【CF827E】Rusty String 调和级数+FFT
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【CF827E】Rusty String 调和级数+FFT，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1887字，纯文字阅读大概需要3分钟。
内容图文
【CF827E】Rusty String
题意：给你一个01串，其中部分字符是‘?‘，?可以是0或1，求所有可能的d，满足存在一种可能得到的01串，在向右移动d格后与自己相同。
$n\le 5\times 10^5$
题解：我们先枚举d，那么一个串符合条件当且仅当：$\forall i \in [0,d), a_i=a_{i+d}=a_{i+2d}=...$，我们可以用fft来判断是否相等。具体地，我们令a串代表正串中的V，b串代表反串中的K，求a和b的卷积c，这样只需要判断$c_d,c_{2d},c_{3d}...$是否都是0就行了。时间复杂度$O(n \log n)$。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#define pi acos(-1.0)
using namespace std;
struct cp
{
double x,y;
cp () {}
cp (double a,double b) {x=a,y=b;}
cp operator + (const cp &a) const {return cp(x+a.x,y+a.y);}
cp operator - (const cp &a) const {return cp(x-a.x,y-a.y);}
cp operator * (const cp &a) const {return cp(x*a.x-y*a.y,x*a.y+y*a.x);}
}l1[1<<20],l2[1<<20];
int n,len,top;
int v[1<<20],sta[500010];
char str[500010];
inline void FFT(cp *a,int f)
{
int i,j,k,h;
for(i=k=0;i<len;i++)
{
if(i>k) swap(a[i],a[k]);
for(j=len>>1;(k^=j)<j;j>>=1);
}
cp t;
for(h=2;h<=len;h<<=1)
{
cp wn(cos(2*pi*f/h),sin(2*pi*f/h));
for(i=0;i<len;i+=h)
{
cp w(1,0);
for(j=i;j<i+h/2;j++) t=w*a[j+h/2],a[j+h/2]=a[j]-t,a[j]=a[j]+t,w=w*wn;
}
}
}
inline void work()
{
scanf("%d%s",&n,str);
for(len=1;len<2*n;len<<=1);
int i,j;
for(i=0;i<n;i++) l1[i].x=(str[i]==‘V‘),l2[i].x=(str[n-i-1]==‘K‘);
FFT(l1,1),FFT(l2,1);
for(i=0;i<len;i++) l1[i]=l1[i]*l2[i];
FFT(l1,-1);
for(i=0;i<len;i++) v[i]=int(l1[i].x/len+0.5);
for(top=0,i=1;i<=n;i++)
{
for(j=(n-1)%i;j<2*n;j+=i) if(v[j]) break;
if(j>=2*n) sta[++top]=i;
}
printf("%d\n",top);
for(i=1;i<=top;i++) printf("%d%c",sta[i],i==top?‘\n‘:‘ ‘);
memset(l1,0,sizeof(l1[0])*(len+1)),memset(l2,0,sizeof(l2[0])*(len+1));
}
int main()
{
int T;
scanf("%d",&T);
while(T--) work();
return 0;
}//3 5 V??VK 6 ?????? 4 ?VK?
原文：https://www.cnblogs.com/CQzhangyu/p/8379578.html
内容总结
以上是互联网集市为您收集整理的【CF827E】Rusty String 调和级数+FFT全部内容，希望文章能够帮你解决【CF827E】Rusty String 调和级数+FFT所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。