Monday, September 16, 2024

# 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;
}

## Celebrating Black History Month:...

As February unfolds, so does the annual celebration of...

## The Path to Self-Mastery:...

Embarking on a journey of self-mastery and breaking free...

## Wizards of Waverly Place...

In a spellbinding announcement, Disney has officially revealed that...

## Jim Irsay’s Reported ‘Suspected...

In a shocking turn of events last month, Jim...

Coachella Valley Music and Arts Festival, one of the...

## 2024 Taiwan Election: Pivotal...

As Taiwan gears up for its 2024 presidential election,...

### Celebrating Black History Month: Past, Future

As February unfolds, so does the annual celebration of Black History Month, a time to reflect on the profound contributions, resilience, and rich cultural...

### The Path to Self-Mastery: Lessons from Book ‘The Mountain Is You’

Embarking on a journey of self-mastery and breaking free from self-sabotage is a transformative process that requires dedication and conscious effort. Brianna Wiest's insightful...

### Wizards of Waverly Place Cast Reunites for Enchanting Revival

In a spellbinding announcement, Disney has officially revealed that the beloved fantasy series "Wizards of Waverly Place" is set for a magical comeback, featuring...

### Jim Irsay’s Reported ‘Suspected Overdose’: A Closer Look

In a shocking turn of events last month, Jim Irsay, the owner of the Indianapolis Colts, was reportedly found unresponsive at his home in...

### Coachella 2024: Iconic headliners, unforgettable musical experience!

Coachella Valley Music and Arts Festival, one of the most iconic and eagerly anticipated music festivals globally, has just dropped its highly anticipated lineup...

### 2024 Taiwan Election: Pivotal Moment in Political Landscape

As Taiwan gears up for its 2024 presidential election, the political landscape is buzzing with anticipation and fervor. With the island nation situated at...

### Michael Strahan’s Daughter’s Medulloblastoma Diagnosis

In a recent and heartbreaking revelation, Michael Strahan, former NFL star and television personality, shared the devastating news of his daughter Isabella's diagnosis with...

### Michigan vs. Washington: The 2024 National Championship Clash

In a highly anticipated matchup, the 2024 National Championship will witness a clash of football titans as the Michigan Wolverines square off against the...

### Jason Kelce: Unmasking the Unconventional NFL Icon

In the world of professional football, where conformity often takes center stage, one player stands out as a beacon of individuality, both on and...