Shiftmul (TLE e output errato)

Aiuto
1

Salve stavo provando a risolvere Shiftmul e penso di essere a buon punto della soluzione ma non riesco a capire come ottenere l’ultima parte delle moltiplicazioni:

#include <bits/stdc++.h>
using namespace std;

int N, K, D;
const int MOD = 1e9 + 7;

int power(long long x, unsigned int y, int p) 
{ 
    int res = 1; 

    x = x % p; 
  
    if (x == 0) return 0;
 
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
 
        y = y >> 1;
        x = (x*x) % p; 
    } 
    return res; 
} 

int prev(int ind) { return (ind + N - D) % N; }
int next(int ind) { return (ind + D) % N; }

vector<int> execute(int n, int k, int d, vector<int> A)
{
    N = n, K = k, D = d;

    vector<int> prefProd(N, 1);
    int ind = 0;
    for (int i = 0; i <= N; ind = prev(ind), i++)
    {
        prefProd[prev(ind)] = (1LL * prefProd[ind] * A[ind]) % MOD;

        // cout << ind << " " << nxtProd[ind] << " " << prefProd[ind] << endl;
    }

    vector<int> B(N);
    for (int i = 0; i < N; i++)
    {
        int laps = K / N;
        int rem = K % N;

        if (D == 0) {B[i] = power(A[i], K, MOD); continue;}

        B[i] = power(prefProd[0], laps, MOD);

        // Qui pensavo di sfruttare il vettore di prodotti prefissi
        // calcolando solo i prodotti nell'intervallo che mi interessa
        int end = (i + rem * D) % N;

        if (prefProd[end] > prefProd[prev(i)])
            B[i] = (1LL * B[i] * prefProd[end] / prefProd[prev(i)]) % MOD;
        else
            B[i] = (1LL * B[i] * prefProd[i] / prefProd[prev(end)]) % MOD;
    }

    return B;
}

Qualche hint?

2

Attento a quando fai le divisioni in modulo. Non puoi dividere così ma (spoiler) devi moltiplicare per l’inverso modulare.

3

Grazie della risposta però non sono comunque riuscito e quindi ho cambiato strategia (chiaramente non ottimale ma con complessità O(N*logN) quindi dovrebbe passare) e comunque non riesco a venirne a capo anche se a livello logico mi sembra tutto giusto:

#include <bits/stdc++.h>
using namespace std;

int N, K, D;
const int MOD = 1e9 + 7;

class SegmentTree 
{
    vector<int> tree;
    int n;
    const int MOD = 1e9 + 7;

public:
    SegmentTree(const vector<int> &arr) 
    {
        n = arr.size();
        tree.resize(4 * n);  // Allocate sufficient space for the segment tree
        build(arr, 0, 0, n - 1);
    }

    void build(const vector<int> &arr, int node, int start, int end) 
    {
        if (start == end) 
        {
            tree[node] = arr[start] % MOD;  // Leaf node
        } 
        else 
        {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = (tree[2 * node + 1] * tree[2 * node + 2]) % MOD;
        }
    }

    int query(int L, int R, int node, int start, int end) 
    {
        if (R < start || L > end) 
        {
            return 1;  // Identity value for multiplication
        }
        if (L <= start && end <= R) 
        {
            return tree[node];
        }
        int mid = (start + end) / 2;
        int left_query = query(L, R, 2 * node + 1, start, mid);
        int right_query = query(L, R, 2 * node + 2, mid + 1, end);
        return (left_query * right_query) % MOD;
    }

    int query(int L, int R) 
    {
        return query(L, R, 0, 0, n - 1);
    }
};

int power(long long x, unsigned int y, int p) 
{ 
    int res = 1; 

    x = x % p; 
  
    if (x == 0) return 0;
 
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
 
        y = y >> 1;
        x = (x*x) % p; 
    } 
    return res; 
} 

int prev(int ind) { return (ind + N - D) % N; }
int next(int ind) { return (ind + D) % N; }

vector<int> execute(int n, int k, int d, vector<int> A)
{
    N = n, K = k, D = d;

    vector<int> seq;
    map<int, int> mp;
    int ind = 0, totProd = 1;
    for (int i = 0; i < N; ind = prev(ind), i++)
    {
        mp[ind] = i;
        seq.push_back(A[ind]);
        totProd = (1LL * totProd * A[ind]) % MOD;

        // cout << ind << " " << i << " " << A[ind] << endl;
    }

    SegmentTree st(seq);

    vector<int> B(N, 1);
    
    int laps = (K-1) / N;
    int rem = (K-1) % N;
    for (int i = 0; i < N; i++)
    {
        if (D == 0) {B[i] = power(A[i], K, MOD); continue;}

        if (laps > 0) B[i] = power(totProd, laps, MOD);

        int final;
        if (i - D * rem < 0) final = N - (abs(i - D * rem) % N);
        else final = i - D * rem;

        if (mp[final] > mp[i])
            B[i] = (1LL * B[i] * st.query(mp[i], mp[final])) % MOD;
        else
            B[i] = (1LL * B[i] * st.query(mp[i], N - 1) * st.query(0, mp[final])) % MOD;
    }

    return B;
}

Consigli? Sto veramente impazzendo ma non mi viene null’altro in mente. Grazie.

4

Quando fai operazioni in modulo è bene usare un tipo di dato che possa contenere le operazioni che ti servono. Se il modulo è circa 10^9, il prodotto di due numeri più arrivare a 10^{18}. Se questa operazione viene fatta all’interno di variabili di tipo int, avrai problemi di overflow.
Usando i long long non avrai problemi!
Non prenderai AC sistemando solo questo ma è sicuramente un problema importante.

5

Quello che il tuo metodo non ottempera in maniera adeguata è soprattutto il caso in cui GCD(N,D) \neq 1 perché, ad esempio, con:
10 K 2
1 2 3 4 5 6 7 8 9 10
il vettore seq restituisce 2 sotto sequenze identiche: 1,9,7,5,3 - 1,9,7,5,3 invece di 1,9,7,5,3 - 2,10,8,6,4 come dovrebbe essere per procedere in maniera corretta.

6

Grazie a tutti delle risposte l’ho risolto, alla fine dovevo controllare il prodotto prefisso per ogni ciclo.