题解 CF827E 【Rusty String】
shadowice1984
2018-08-14 07:56:49
人傻常数大说的就是我~
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;
}
```