#include<bits/stdc++.h>
#define pi acos(-1)
#define maxn 1148576
using namespace std;
typedef long long ll;
char s[maxn];
int n;
int res[maxn];
struct node{double x,y;}a[maxn],b[maxn],w[2][maxn];
node operator +(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator -(node a,node b){return (node){a.x-b.x,a.y-b.y};}
node operator *(node a,node b){return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
void init(int k){
for(int i=0;i<=k;i++){
w[0][i]=(node){cos(2*pi/k*i),sin(2*pi/k*i)};
w[1][i]=w[0][i];
w[1][i].y*=-1;
}
}
void fft(node x[],int k,int v){
for(int i=0,j=0;i<k;i++){
if(i>j)swap(x[i],x[j]);
for(int l=(k>>1);(j^=l)<l;l>>=1);
}
for(int i=2;i<=k;i<<=1){
for(int j=0;j<k;j+=i){
for(int l=0;l<(i>>1);l++){
node tmp=x[j+l+(i>>1)]*w[v][k/i*l];
x[j+l+(i>>1)]=x[j+l]-tmp;
x[j+l]=x[j+l]+tmp;
}
}
}
if(v){
for(int i=0;i<k;i++)x[i].x/=1.0*k;
}
}
vector <int> ans;
void solve(){
scanf(“%d”,&n);scanf(“%s”,s+1);ans.clear();
int k=1;while(k<=(n+n))k<<=1;init(k);
for(int i=0;i<=k;i++)res[i]=0;
for(int i=0;i<=k;i++)a[i].x=b[i].x=a[i].y=b[i].y=0;
for(int i=1;i<=n;i++){
if(s[i]==’V’)a[i-1].x=1;
else if(s[i]==’K’)b[n-i+1].x=1;
}
fft(a,k,0);fft(b,k,0);for(int i=0;i<k;i++)a[i]=a[i]*b[i];fft(a,k,1);
for(int i=1;i<=n;i++){
if((int)(a[n-i].x+0.5)==0 && (int)(a[n+i].x+0.5)==0)res[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=i<<1;j<=n;j+=i){
res[i]&=res[j];
if(!res[i])break;
}
if(res[i])ans.push_back(i);
}
printf(“%d\n”,(int)ans.size());
for(int i=0;i<(int)ans.size();i++)printf(“%d “,ans[i]);
puts(“”);
}
int main(){
int T;scanf(“%d”,&T);
while(T–){
solve();
}
return 0;
}
Codeforces Round #423 (Div. 1, rated, based on VK Cup Finals), problem: (E) Rusty String Solution in C/C++
#include<bits/stdc++.h>
#define pi acos(-1)
#define maxn 1148576
using namespace std;
typedef long long ll;
char s[maxn];
int n;
int res[maxn];
struct node{double x,y;}a[maxn],b[maxn],w[2][maxn];
node operator +(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator -(node a,node b){return (node){a.x-b.x,a.y-b.y};}
node operator *(node a,node b){return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
void init(int k){
for(int i=0;i<=k;i++){
w[0][i]=(node){cos(2*pi/k*i),sin(2*pi/k*i)};
w[1][i]=w[0][i];
w[1][i].y*=-1;
}
}
void fft(node x[],int k,int v){
for(int i=0,j=0;i<k;i++){
if(i>j)swap(x[i],x[j]);
for(int l=(k>>1);(j^=l)<l;l>>=1);
}
for(int i=2;i<=k;i<<=1){
for(int j=0;j<k;j+=i){
for(int l=0;l<(i>>1);l++){
node tmp=x[j+l+(i>>1)]*w[v][k/i*l];
x[j+l+(i>>1)]=x[j+l]-tmp;
x[j+l]=x[j+l]+tmp;
}
}
}
if(v){
for(int i=0;i<k;i++)x[i].x/=1.0*k;
}
}
vector <int> ans;
void solve(){
scanf(“%d”,&n);scanf(“%s”,s+1);ans.clear();
int k=1;while(k<=(n+n))k<<=1;init(k);
for(int i=0;i<=k;i++)res[i]=0;
for(int i=0;i<=k;i++)a[i].x=b[i].x=a[i].y=b[i].y=0;
for(int i=1;i<=n;i++){
if(s[i]==’V’)a[i-1].x=1;
else if(s[i]==’K’)b[n-i+1].x=1;
}
fft(a,k,0);fft(b,k,0);for(int i=0;i<k;i++)a[i]=a[i]*b[i];fft(a,k,1);
for(int i=1;i<=n;i++){
if((int)(a[n-i].x+0.5)==0 && (int)(a[n+i].x+0.5)==0)res[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=i<<1;j<=n;j+=i){
res[i]&=res[j];
if(!res[i])break;
}
if(res[i])ans.push_back(i);
}
printf(“%d\n”,(int)ans.size());
for(int i=0;i<(int)ans.size();i++)printf(“%d “,ans[i]);
puts(“”);
}
int main(){
int T;scanf(“%d”,&T);
while(T–){
solve();
}
return 0;
}
