AtCoder ARC #048 : C - 足の多い高橋君

Cで大苦戦。Dは解ける問題だったのに、Cで苦戦して時間切れ。
http://arc048.contest.atcoder.jp/tasks/arc048_c

問題

N個の01で構成される文字列S[i]を考える。
各文字列の長さL[i]が与えられる。

異なる２つの文字列S[x],S[y]について、S[x]にS[y]を反転させたものを連結した場合、回文となるようにしたい。
各S[i]の取り方は何通りあるか。

解法

まずLを昇順ソートする。
S[i]の先頭L[0]文字はそれぞれ中身はそろってさえいれば何でも良い。
よって先頭L[0]文字分2^(L[0])通りは任意に選ぶことができる。

各文字残りL[i]-L[0]の最大公約数をgとする。
g文字の回文の作り方は2^(ceil(g/2))通りなので、合わせて2^(L[0]+ceil(g/2))通り。

ではなぜL[i]-L[0]の最大公約数を取るか。
各文字S[i]に対し、先頭min(L[i],L[y])文字まで内容が確定していたとする。L[x]＜L[y]＜L[z]となるx,y,zを考えよう。
S[x]+rev(S[z])を連結させると回文であり、かつS[z]の先頭L[y]文字が確定しているので、S[x]+rev(S[z])の先頭L[y]文字も確定する。
L[x]＜L[y]なのだから、S[z]の末尾(L[y]-L[x])文字が確定する。

次にS[y]+rev(S[z])を考えると、S[y]は確定しており、かつS[z]の末尾(L[y]-L[x])文字は各停しているので、S[y]+rev(S[z])の先頭L[y]+(L[y]-L[x])が確定する。
よってS[z]の先頭はL[y]+(L[y]-L[x])文字確定した。
そのため他の文字列もL[y]+(L[y]-L[x])文字まで確定する。

このように考えると、すでに確定している文字S[a],S[b]に対し、GCD(L[a]-L[b])ずつ確定文字列を伸ばすことができる。
また確定分の文字列は反転しても回文判定に問題ないよう、回文でなければならない。

…ともろもろ考えると、(L[i]-L[0])全部のGCDを取ったものが回文である必要があるので2^ceil(g/2)通りだけ文字列の取り方の自由度がある。

int N;
ll L[101010];
ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i];
	sort(L,L+N);
	N=unique(L,L+N)-L;
	
	ll ret=L[0];
	ll g=0;
	for(i=1;i<N;i++) g=__gcd(L[i]-L[0],g);
	ret+=(g+1)/2;
	cout<<modpow(2,ret)<<endl;
}

まとめ

考察はめんどいけど実装は簡単。