P11404 [RMI 2020] 蝶变 / Brperm 题解

· · 题解

孩子们，调了一晚上结果数据锅了，不保证 i+2^k\le N /ll

考虑字符串哈希的式子：

f(B)=\sum_{i=0}^{n-1}s_iB^i

可以把它当成生成函数来理解，那么 f(B^2) 相当于把字符串中每个字符后面插了一个空格。

然后考虑题目中的变换，现在要求区间 [l,l+2^k) 变换后的哈希值，记为 f(x)，假设 [l,l+2^{k-1}),[l+2^{k-1},l+2^k) 是变换好的，它们变换后的哈希值分别记为 f_0(x),f_1(x)，那么可以得出 f(B)=f_0(B^2)+Bf_1(B^2)。

暴力做就是 \mathcal O(n\log^2n) 的。

然后没有人规定过字符串哈希的 B 必须是固定的对吧。所以我们在 [i,i+2^k) 使用 B^{2^{19-k}} 当底数就可以做到 \mathcal O(n\log n) 了。

随便写写就最优解了？？？

#define maxn 501000
const int P=1000000007;
int pw[20];
int f[20][maxn];
int g[maxn];
bitset<maxn>ok[20];
int n;
void init(int N, const char s[]) {
    n=N;
    vector<int>p(26);
    rep(i,0,25)p[i]=i;
    shuffle(p.begin(),p.end(),rnd);
    rep(j,0,19)ok[j].set();
    pw[19]=20071230;
    per(i,18,0)pw[i]=1ll*pw[i+1]*pw[i+1]%P;
    rep(i,0,N-1)f[0][i]=p[s[i]-'a'];
    rep(j,1,19) {
        int B=pw[j];
        for(int i=0; i+(1<<j)-1<=N-1; ++i) {
            f[j][i]=f[j-1][i]+1ll*f[j-1][i+(1<<(j-1))]*B%P;
            if(f[j][i]>=P)f[j][i]-=P;
        }
        g[N-1]=p[s[N-1]-'a'];
        per(i,N-2,0)g[i]=(1ll*g[i+1]*B%P+p[s[i]-'a'])%P;
        for(int i=0; i+(1<<j)-1<=N-1; ++i) {
            ok[j][i]=(f[j][i]==(g[i]-1ll*g[i+(1<<j)]*pw[0]%P+P)%P);
        }
    }
}
int query(int i, int k) {
    if(i+(1<<k)>n)return 0;
    return ok[k][i];
}