P12523 [Aboi Round 1] Nomad

· · 题解

思路：

每次令 x' = x^2 + 2x，两边同时 +1，可以得到 (x' + 1) = (x + 1)^2；于是一个数 x 进行 k 次操作，相当于变成：

x' = (x + 1)^{2^k} - 1

而询问是一个区间 [l, r] 内的所有子序列的积的和，即每个数选或不选两种情况，最后累乘起来，答案应该是：

\prod_{i = l}^r (1 + a_i) - 1

然后设 w_i 表示 i 位置进行操作的次数，于是答案可以表示为：

\prod_{i = 1}^n (a_i + 1)^{2^{w_i}} - 1

于是，我们相当于要支持以下两种操作：

于是直接使用线段树维护，每个节点开一个懒标记 tag，表示这个区间每个位置是 a_i \gets a_i^{tag}。

时间复杂度是 O(n \log n \log p)，只能获得 70pts。

link。

考虑如何优化，瓶颈在于每次都要快速幂，发现都是在指数上进行乘法操作，如果所有数的底数一样的话，那么就只需要对指数维护乘法。

所以考虑找一个 p 的原根 g，将 a_i 表示成 g^{b_i}，于是只需要支持 b 的区间乘法，区间和的查询，用线段树是简单做的。

然后就变成了 P11175 【模板】基于值域预处理的快速离散对数 这个问题，可以直接套用模版；或者使用这个题的前面部分算法，调 BSGS 的块长为 \sqrt{np} 也行。

时间复杂度为 O(\frac{p^{\frac{3}{4}}}{\log^{\frac{1}{2}} p} + (n + q) \log p + n \log n) 或者 O(\sqrt{np} + n \log n + (n + q) \log p)。

完整代码：

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6 + 10, mod = 1e9 + 7;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
namespace Quick_BSGS{
    const int N = 4e4 + 10;
    int p, g, pp, h, _lg1, m, cnt, B;
    int lg[N], prime[N];
    bool vis[N];
    gp_hash_table<int, int> mp;
    inline int qpow(int a, int b, int mod){
        int ans = 1;
        while(b){
            if(b & 1)
                ans = 1ll * ans * a % mod;
            a = 1ll * a * a % mod;
            b >>= 1;
        }
        return ans;
    }
    inline int ask(int b){
        if(b == 1)
            return 0;
        b = qpow(b, p - 2, p);
        int now = b;
        for(int i = 1; i <= (p / B) + 1; ++i){
            now = 1ll * now * h % p;
            if(mp.find(now) != mp.end())
                return i * B - mp[now];
        }
        return -1;
    }
    inline void init(int _p, int _g){
        p = _p, g = _g;
        pp = p - 1;
        B = sqrt(p * sqrt(p) / log(sqrt(p)));
        int now = 1;
        for(int i = 0; i < B; ++i){
            mp[now] = i;
            now = 1ll * now * g % p;
        }
        h = now;
        _lg1 = ask(p - 1);
        m = sqrt(p) + 1;
        lg[1] = ask(1);
        for(int i = 2; i <= m; ++i){
            if(!vis[i]){
                prime[++cnt] = i;
                lg[i] = ask(i);
            }
            for(int j = 1; j <= cnt && i * prime[j] <= m; ++j){
                vis[i * prime[j]] = 1;
                lg[i * prime[j]] = (lg[i] + lg[prime[j]]) % pp;
                if(i % prime[j] == 0)
                    break;
            }
        }
//      for(int i = 1; i <= 10; ++i){
//          cerr << i << ' ' << lg[i] << ' ' << qpow(g, lg[i], p) << '\n';
//      }
//      putchar('\n');
    }
    inline int query(int x){
        if(x <= m)
            return lg[x];
        int r = p % x, q = (p - r) / x;
        if(r <= x - r)
            return ((_lg1 + query(r)) % pp - lg[q] + pp) % pp;
        return (query(x - r) - lg[q + 1] + pp) % pp;
    }
};
struct Node{
    int l, r;
    int sum, tag;
}X[N << 2];
int n, q, k, l, r, op, type, all, ans;
int a[N];
inline int qpow(int a, int b, int p){
    int ans = 1;
    while(b){
        if(b & 1)
            ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return ans;
}
inline void pushup(int k){
    X[k].sum = (X[k << 1].sum + X[k << 1 | 1].sum) % (mod - 1);
}
inline void mul(int k, int v){
    X[k].sum = 1ll * X[k].sum * v % (mod - 1);
    X[k].tag = 1ll * X[k].tag * v % (mod - 1);
}
inline void push_down(int k){
    if(X[k].tag != 1){
        mul(k << 1, X[k].tag);
        mul(k << 1 | 1, X[k].tag);
        X[k].tag = 1;
    }
}
inline void build(int k, int l, int r){
    X[k].l = l, X[k].r = r;
    X[k].tag = 1;
    if(l == r){
        X[k].sum = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    pushup(k);
}
inline void update(int k, int l, int r, int v){
    if(X[k].l == l && r == X[k].r){
        mul(k, v);
        return ;
    }
    push_down(k);
    int mid = (X[k].l + X[k].r) >> 1;
    if(r <= mid)
      update(k << 1, l, r, v);
    else if(l > mid)
      update(k << 1 | 1, l, r, v);
    else{
        update(k << 1, l, mid, v);
        update(k << 1 | 1, mid + 1, r, v);
    }
    pushup(k);
}
inline int query(int k, int l, int r){
    if(X[k].l == l && r == X[k].r)
      return X[k].sum;
    push_down(k);
    int mid = (X[k].l + X[k].r) >> 1;
    if(r <= mid)
      return query(k << 1, l, r);
    else if(l > mid)
      return query(k << 1 | 1, l, r);
    else
      return (query(k << 1, l, mid) + query(k << 1 | 1, mid + 1, r)) % (mod - 1);
}
int main(){
    Quick_BSGS::init(mod, 5);
    n = read(), q = read(), type = read();
    for(int i = 1; i <= n; ++i)
      a[i] = Quick_BSGS::query(read() + 1);
    build(1, 1, n);
    while(q--){
        op = read(), l = read(), r = read();
        if(op == 1){
            k = read();
            k = qpow(2, k, mod - 1);
            update(1, l, r, k);
//          for(int i = l; i <= r; ++i)
//            a[i] = qpow(a[i], k, mod);
        }
        else{
            int ans = qpow(5, query(1, l, r), mod);
//          for(int i = l; i <= r; ++i)
//              ans = 1ll * a[i] * ans % mod;
            --ans;
            if(type)
              all ^= ans;
            else{
                write(ans);
                putchar('\n');
            }
        }
    }
    if(type)
      write(all);
    return 0;
}