Codeforces Round #423E: Rusty String

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自体ははライブラリ化すれば問題ない。
帰着させるところが難しい。
少しずつずれたものを考える時に有効?