• 给定a_{1\cdots n}p,多次询问\prod\limits_{i=l}^ra_ip取模的值,强制在线
  • n\leq 10^6 , q\leq 10^7

sol

黑科技…

静态区间查询,可以想到ST表.
但ST表的区间会互相覆盖,不能满足这题的要求.
也不能前缀和因为p可能不是质数.

于是我们有一个类似ST表的技术:

A_{k,i}=\prod\limits_{j=\left\lfloor\frac i{2^k}\right\rfloor2^k}^ia_j,B_{k,i}=\prod\limits_{j=i}^{\left\lceil\frac{i+1}{2^k}\right\rceil2^k-1}a_j

A_{k,i}表示的是(\leq i的最大的2^k的倍数)到i这一段数的乘积
B_{k,i}表示的是i到(\gt i的最小的2^k的倍数-1)这一段数的乘积
这两个都可以O(n\log_2n)预处理

对于询问[l,r],如果l=r那么答案就是a_l,下面讨论l\lt r的情况

如果我们可以找到一个k,使得[l+1,r]中只有一个2^k的倍数,那么B_{k,l}A_{k,r}就是答案

容易验证一个满足要求的k就是\log_2\left(\text{highbit}(r\text{ xor }l)\right),然后这题就做完了…

Code

#include 
using namespace std;
const int N = 2e6 + 50;

# define rg register 
inline int read(int &x) {
    x = 0; char c = getchar();
    for(; !isdigit(c); c = getchar());
    for(;  isdigit(c); c = getchar())
        x = x * 10 + c - '0';
}

int cas, n, q, mod, l, r, a[N], hb[N];
int A[21][N], B[21][N];

inline int mul(int a, int b) {
    return (long long) a * b % mod;
}
inline int Ceil(int x, int k) { // ceil(x / (2 ^ k))
    return (x & ((1 << k) - 1)) ? (x >> k) + 1 : x >> k;
}
inline int Floor(int x, int k) { // floor(x / (2 ^ k))
    return x >> k;
}

int query(int l, int r) {
    if(l == r) return a[l];
    static int k;
    k = hb[r ^ l];
    return mul(B[k][l], A[k][r]);
}
namespace sol {
    int b[320010];
    int main() {
        for(int i = 0; i < q / 64 + 2; i++)
            scanf("%d", b + i);
        int x = 0;
        for(int i = 0; i < q; i++){
            if(!(i & 63)){
                l = (b[i >> 6] + x) % n;
                r = (b[(i >> 6) + 1] + x) % n;
            } else {
                l = (l + x) % n;
                r = (r + x) % n;
            }
            if(l > r) swap(l, r);
            x = (query(l + 1, r + 1) + 1) % mod;
        }
        return x;
    }
}

int main() {
    hb[1] = 0;
    for(int i = 2; i <= 2e6; ++i) {
        hb[i] = hb[i - 1];
        if(i >> (hb[i - 1] + 1))
            ++hb[i];
    }
    for(cin >> cas; cas--; ) {
        read(n), read(mod), read(q);
        for(rg int i = 1; i <= n; ++i) {
            read(a[i]), a[i] %= mod;
            A[0][i] = B[0][i] = a[i];
        }
        for(int j = 1; 1 << j <= n; ++j) {
            A[j][0] = B[j][n + 1] = 1;
            for(int i = 1; i <= n; ++i) 
                A[j][i] = mul(a[i], Floor(i, j) << j == i ? 1 : A[j][i - 1]);
            for(int i = n; i >= 1; --i) 
                B[j][i] = mul(a[i], Ceil(i + 1, j) << j == (i + 1) ? 1 : B[j][i + 1]);
        }
        cout << sol :: main() << '\n';
    }
    return 0;
}