TopCoder SRM 592 Div1 Hard SplittingFoxes2

問題

n項からなる数列aがある。
これに対してn項からなる数列P={P[0], P[1], ...,P[n-1]}で表される操作を行うと、
a[0] := a[0] * P[0] + a[1] * P[n-1] + a[2] * P[n-2] + …
a[1] := a[0] * P[1] + a[1] * P[0] + a[2] * P[n-1] + …
…

のように変化する。
（aはaとPの巡回たたみこみになる）

ただし、PはP[i] = P[(n-i)%n]を満たすものとする。
Pを(1, 0, 0, ..., 0)に二回適用した後のaが与えられるとき、
Pとしてありえるもののうち、辞書順最小のものを求めよ。
ないときは-1を返せ。

制約条件

n≦25
a[i]≦1000000

方針

＊をたたみこみの演算とすると、
a = P＊P
なので、F(x)をxの離散フーリエ変換とすれば
F(a) = F(P) * F(P)（要素同士の通常の積）
より、
F(a)[i] = ±sqrt(F(P)[i])になる。

プラスマイナスの自由度が2^nあるが、
Pが偶関数（というのか？P[i] = P[(n-i)%n]のこと）
だとF(P)も偶関数になるという性質があるらしいので、自由度は2^(n/2+1)通りしかない。

ので、全通りプラスマイナスを試して、
逆変換したものが元に戻っているかを見ればよい。

フーリエ変換は要素が25しかないので、FFTを使わず愚直に計算して間に合う。
というか、偶関数性を使う都合上長さを2のべき乗ではなくnでフーリエ変換をしなくてはならないので、FFTだと大変。

ソースコード

class SplittingFoxes2 {
	public:
	vector <int> getPattern(vector <int> amount) {
		
		n = amount.size();
		int m = n / 2 + 1;
		rep(i, n) w[i] = polar(1.0, -2 * PI * i / n);
		
		vi ans;
		vector<P> x;
		
		rep(i, n) x.pb(amount[i]);
		x = dft(x);
		rep(i, n){
			double r = abs(x[i]);
			double t = arg(x[i]);
			
			x[i] = polar(sqrt(r), t / 2);
		}
		rep(i, n) w[i] = polar(1.0, 2 * PI * i / n);
		
		
		rep(i, 1 << m){
			vector<P> y = x;
			
			rep(j, n){
				if(j < m && (i & 1 << j) || j >= m && (i & 1 << (n - j)) ) y[j] *= -1.0;
			}
			y = dft(y);
			
			vi z;
			rep(j, n) z.pb((int)(y[j].real() / n + 0.48));
			if(ok(z, amount) && (ans.empty() || ans > z)) ans = z;
		}
		
		if(ans.empty()) ans.pb(-1);
		return ans;
	}
};