http://codeforces.com/contest/827/problem/E
初FFTです
k periodである条件は|i-j|%k=0かつS[i]とS[j]がそれぞれVとKであるi,jが存在しないことである。
そこで、S[i]='V'ならばA[i]=1でありそれ以外の要素は0である配列Aと、S[N-i-j]='V'ならばB[i]=1であり、それ以外の要素は0である配列Bをとる。
AとBをFFTして得られた配列Cのi番目の要素C[i]について
C[i]>0 <=> A[j]=1かつB[i-j]=1 <=> S[j]='V'かつS[n-i+j]='K'である。
よってk periodであるためには
(n-i+j)-j=n-iがkで割り切れるすべてのiについてC[i]=0が成立すれば良い。
計算量はfftでO(NlogN)、最後のC[i]=0を確かめるところでΣ(N/k)=O(NlogN)なので間に合う。
struct FFT { void fft(vector<comp>& v, bool rev = false) { //v.size() == (1 << x) int n = sz(v), i, j; for(i = 0, j = 1; j < n - 1; j++) { for(int k = n >> 1; k > (i ^= k); k /= 2); if(i > j) swap(v[i], v[j]); } for(int m = 2; m <= n; m *= 2) { comp wr = polar(1.0, (rev? -1 : 1) * 2.0 * PI / m); for(int i = 0; i < n; i += m) { comp w(1, 0); rep(j, 0, m / 2) { comp f0 = v[i + j], f1 = w * v[i + j + m / 2]; v[i + j] = f0 + f1; v[i + j + m / 2] = f0 - f1; w *= wr; } } } if(rev) rep(i, 0, n) v[i] *= 1.0 / n; } vector<int> get(const vector<int>& A, const vector<int>& B) { int n = 1; while(n < sz(A) + sz(B)) n *= 2; vector<comp> a(n), b(n); rep(i, 0, sz(A)) a[i] = comp(A[i], 0); rep(i, 0, sz(B)) b[i] = comp(B[i], 0); fft(a); fft(b); rep(i, 0, n) a[i] *= b[i]; fft(a, true); vector<int> res(n); rep(i, 0, n) res[i] = (int)(a[i].real() + 0.5); return res; } }; FFT F; void solve() { int Q; cin >> Q; while(Q--) { int N; cin >> N; string str; cin >> str; vector<int> A(N, 0), B(N, 0); rep(i, 0, N) { if(str[i] == 'V') A[i] = 1; else if(str[i] == 'K') B[N - 1 - i] = 1; } vector<int> v = F.get(A, B); //debug(v); vector<int> ans; rep(k, 1, N) { bool ok = true; for(int m = 0; N / k * k + N - 1 - k * m >= 0; m++) { if(v[N / k * k + N - 1 - k * m]) { ok = false; break; } } if(ok) ans.push_back(k); } ans.push_back(N); cout << sz(ans) << "\n"; rep(i, 0, sz(ans)) cout << ans[i] << " "; cout << "\n"; } }
fft自体ははライブラリ化すれば問題ない。
帰着させるところが難しい。
少しずつずれたものを考える時に有効?