Fork me on GitHub

「PKUSC2018」神仙的游戏 NTT 生成函数 字符串

发表于 | 分类于
字数统计: 835字 | 阅读时长 ≈ 5分钟

Links there:PKUSC2018-神仙的游戏

先向考场只做了18分的我凭吊.

上次考完听说这是个多翔式的题,但似乎一直忘了去思考为什么…所以就当补上了吧.

题意

给出一个由 $0$ , $1$ , $?$ 构成的串 $s$ .问号可以换成 $0,1$,现在定义$f(len)$ 表示 $s$ 中长度为 $len$ 的前缀是否能够成为$border$,如果是则值为$1$,否则为$0$.

求异或和

思路

寻找所谓的$border$的性质,如果对于一个长度为$len$的border存在,当且仅当

$\forall i∈[1,n−len]$ 有 $s[i] = s[n-len+1]$

等价于在Mod $n-len$的意义下分组,每一组的所有01必须相同。

那么对于每一对01来说对于任意的$x,x|(pos_0 - pos_1)$都不可行.

考虑求出所有的$(pos_0 - pos_1)$然后暴力枚举他的倍数就行啦,复杂度是$O(n lnn)$

考虑构造这样两个生成函数

$f1(x)=\sum{i=0}^{n}[s_i== 0] x^i$

$f2(x)=\sum{i=0}^n[s_{n-i}==1]x^i$

构造卷积$f_1 * f_2 = f_3$

在$f_3$中发现$pos_0-pos_1$对应的就是$pos_0-pos_1+n$

$NTT$优化后在$f_3$中统计答案就行啦.复杂度是$O(nlogn)$,这也是总复杂度.

果然是神仙的游戏!

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define se second
using namespace std;
#define int long long

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
const int MAXN = 2e6+100;
const int Mod = 998244353;
int A[MAXN],B[MAXN],Rev[MAXN],N,l=0,w = 3;
char s[MAXN];
///------------------head------------------
void NTT(int *a,int op)
{
    for(int i=0;i<N;i++) if(i<Rev[i]) swap(a[i],a[Rev[i]]);
    for(int i=1;i<N;i<<=1)
    {
        int wn = quickpow(w,op==1?(Mod-1)/(2*i):Mod-1-(Mod-1)/(2*i),Mod),t,w;
        for(int j=0;j<N;j+=i<<1)
        {
            w=1;
            for(int k=0;k<i;k++)
            {
                t=w*a[i+j+k]%Mod;
                w=w*wn%Mod;
                a[i+j+k]=(a[j+k]-t+Mod)%Mod;
                a[j+k]=(a[j+k]+t)%Mod;
            }
        }
    }
    if(~op) for(int i=0,inv=getinv(N,Mod);i<N;i++) a[i]=a[i]*inv%Mod;
}
int ans = 0;
signed main(signed argc, char *argv[]){
    scanf("%s",s);
    int Len = strlen(s);
    for (N=1;N<Len+Len;N<<=1) ++l;
    for (int i=0;i<N;++i) Rev[i] = (Rev[i>>1] >> 1) | ((i&1)<<(l-1));
    for (int i=0;i<Len;++i) A[i] = s[i] == '0',B[i] = s[Len-i-1] == '1';
    NTT(A,1); NTT(B,1);
    for (int i=0;i<N;i++) A[i]=A[i]*B[i]%Mod;
    NTT(A,-1);
    ans = Len * Len;
    for (int i = 1; i < Len; i++){
        ans ^= (Len-i) * (Len - i);
        for (int j = i; j < Len; j += i)
        if (A[Len-1+j] || A[Len-1-j]) {ans ^= (Len - i) * (Len - i); break;}
    }
    printf("%lld\n",ans);
    return 0;
}

/* Examples: */
/*
1?0?
*/

/*
17
*/