AtCoder ARC #147 : F - Again ABC String

シンプルな問題設定ではあるのだけども。
https://atcoder.jp/contests/arc147/tasks/arc147_f

問題

整数N,X,Y,Zが与えられる。
ABCで構成されるN文字の文字列Sのうち、prefix i文字目までのA,B,Cの個数をA(i),B(i),C(i)とする。

• A(i)-B(i)≦X
• B(i)-C(i)≦Y
• C(i)-A(i)≦Z

を満たすSの個数の偶奇を求めよ。

解法

以下のように言い換える。
M=X+Y+Z+3点からなる円周上の、0,X+1.X+Y+2の点に駒が置いてある。
1手ごとに駒を一つ選んで時計回りに動かすとき、駒の位置が変わらない方法は何通りか。

i回駒を動かしたとき、2個目と1個目の駒の位置の差と、3個目と2個目の駒の位置の差を状態とするDPを考えるとよいが、これだと状態がO(NM^2)ありとても間に合わない。
鏡像法を用いると、(x+1+1/x)^N mod (x^M-1)を何回か解く問題に式変形できる。

Mが小さければバイナリ法で解けばよいし、Mが大きい場合はx^(K+nM)の係数の和を取るようにすればよい。

int T;
ll N,X,Y,Z,M;
ll from[101010],to[101010];
ll hoge(ll N,ll V) {
	int i,j;
	if(M<=100000) {
		ZERO(from);
		from[0]=1;
		FOR(i,30) if(N&(1<<i)) {
			int a=(1<<i);
			FOR(j,M) {
				to[j]=from[j]^from[(j+a)%M]^from[((j-a)%M+M)%M];
			}
			swap(from,to);
		}
		return from[V];
	}
	else {
		int ret=0;
		for(ll t=(N+V)%M;t<=2*N;t+=M) {
			int from[2]={1,0};
			FOR(i,40) {
				int to[4]={};
				int b=((t)>>i)&1;
				if(N&(1LL<<i)) {
					
					// not
					to[0]^=from[0];
					to[1]^=from[1];
					// 2^i
					to[1]^=from[0];
					to[2]^=from[1];
					// 2^(i+1)
					to[2]^=from[0];
					to[3]^=from[1];
					
					from[0]=to[b];
					from[1]=to[b|2];
					
				}
				else {
					from[0]=from[b];
					from[1]=0;
				}
			}
			ret^=from[0];
		}
		return ret;
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>X>>Y>>Z;
		M=X+Y+Z+3;
		int ret=1^hoge(N,X+Y+2)^hoge(N,X+1)^hoge(N,Y+1);
		cout<<ret<<endl;
	}
}

まとめ

こういう問題時間内に解けるようになるには何をすればいいんだろ。