题解 CF827E 【Rusty String】

shadowice1984

2018-08-14 07:56:49

Solution

人傻常数大说的就是我~ 1e6的fft也是醉了…… ________________ 这题是个套路题,多项式乘法优化带通配符的字符串匹配 题目意思简单明了,给你一个字符集为2的字符串,带不确定符,求每一个可能出现的“period”长度,“period”长度为d意思是如果将这个字符串右移d位之后这个字符串和原来的字符串是否可以匹配 那么我们来看一下这道题…… 假设我们要确定这个串是否有长度为d的"period",实际上就是在确定这个式子是否为0(显然这是一个暴力式子) $$\sum_{i}[S_{i} \neq S_{i+d}]$$ 然后我们将整个串翻转一下得到一个串$S^{'}$ $$\sum_{i}[S_{i} \neq S_{n-1-i-d}^{'}]$$ 重新写一下变成了 $$\sum_{i+j=n-1-d}[S_{i} \neq S_{j}^{'}]$$ 似乎这式子非常像卷积?~~(不,就是卷积)~~ 问题来了我们怎么将不等号写成乘法的形式呢? $$\sum_{i+j=n-1-d}[S_{i}==V][S_{j}^{'}==K ]+[S_{i}==K][S_{j}^{'}==V ]$$ 反正字符集只有两个,暴力枚举一下就行了 然后你愉快的打了个fft/ntt然后算了两遍卷积加起来却发现自己连样例都没过…… ~~excuse me?~~ 然后我们发现其实 $$[S_{i} \neq S_{j}^{'}] \neq [S_{i}==V][S_{j}^{'}==K ]+[S_{i}==K][S_{j}^{'}==V ]$$ 为什么呢? 因为我们的问号是不确定的字符,并不是通配符,请注意这两个东西是不一样的,**未知不等于通配** 煮个栗子 V??VK @@V??VK 可以看到如果是?是通配符的话这个字符串是有2的“period”的 但是由于?不是通配符,所以第二个?由于在匹配的时候既是V又是K所以凉掉了 ~~笑容逐渐凝固~~ 然后我们发现这种特例还是可以抢救一下的,发现一个性质是如果出现了这种假的匹配情况的话,他的倍数中至少有一个连假的"period"都不是 这个性质的证明可以自己画图理解一下 所以就是卷积两遍加起来然后判一下每位置是不是假的"period"就行了 ~~fft忘了写的ntt~~ 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=1048576+10;typedef unsigned long long ll;const ll mod=998244353; const int U=1048576;int rv[N];ll rt[2][22];int n;char mde[N];int T; inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;} inline void ntt(ll* a,int o,int len) { for(int i=0;i<len;i++)if(i<rv[i])swap(a[i],a[rv[i]]); for(int k=1,j=1;k<len;k<<=1,j++) for(int s=0;s<len;s+=(k<<1)) for(int i=s,w=1;i<s+k;i++,w=w*rt[o][j]%mod) {ll a0=a[i];ll a1=a[i+k]*w%mod;a[i]=(a0+a1)%mod,a[i+k]=(a0+mod-a1)%mod;} if(o){ll inv=po(len,mod-2);for(int i=0;i<len;i++)(a[i]*=inv)%=mod;} }ll f1[N];ll f2[N];ll f3[N]; inline void solve() { scanf("%d",&n);scanf("%s",mde);//构造多项式之后卷积两遍加起来 int d=0;int le=1;for(;le<(n<<1);le<<=1,d++); for(int i=0;i<le;i++)rv[i]=(rv[i>>1]>>1)|((i&1)<<(d-1)); for(int i=0;i<n;i++)f1[i]=(mde[i]=='V'); for(int i=0;i<n;i++)f2[i]=(mde[n-1-i]=='K'); ntt(f1,0,le);ntt(f2,0,le);for(int i=0;i<le;i++)(f1[i]*=f2[i])%=mod; ntt(f1,1,le);reverse(f1,f1+n);for(int i=0;i<n;i++)f3[i]+=f1[i]; for(int i=0;i<le;i++)f1[i]=0;for(int i=0;i<le;i++)f2[i]=0; for(int i=0;i<n;i++)f1[i]=(mde[i]=='K'); for(int i=0;i<n;i++)f2[i]=(mde[n-i-1]=='V'); ntt(f1,0,le);ntt(f2,0,le);for(int i=0;i<le;i++)(f1[i]*=f2[i])%=mod; ntt(f1,1,le);reverse(f1,f1+n);for(int i=0;i<n;i++)f3[i]+=f1[i]; int cnt=0; for(int i=1;i<=n;i++)//特判一下特殊情况 for(int j=2*i;j<=n;j+=i)if(f3[j]!=0){f3[i]=-1;break;} for(int i=1;i<=n;i++)cnt+=(f3[i]==0);printf("%d\n",cnt); for(int i=1;i<=n;i++)if(f3[i]==0)printf("%d ",i);printf("\n"); for(int i=0;i<=n;i++)f3[i]=0; for(int i=0;i<le;i++)f1[i]=0;for(int i=0;i<le;i++)f2[i]=0; } int main() { for(int j=1,t=(mod-1)/2;j<=20;t>>=1,j++)rt[0][j]=po(3,t); for(int j=1,t=(mod-1)/2;j<=20;t>>=1,j++)rt[1][j]=po(332748118,t);//拜拜程序~ scanf("%d",&T);for(int z=1;z<=T;z++)solve();return 0; } ```