AtCoder ARC #064 : F - Rotated Palindromes

ポリアにとらわれすぎた。
http://arc064.contest.atcoder.jp/tasks/arc064_d

問題

以下の数列Aは何通りあるか。

• N個の要素からなり、それぞれ1～Nである。
• 回転させると回文になる。

解法

まずは回転させない状態を考える。
数列の最短周期がdとなる組み合わせをF(d)とする。
全体が回文の条件から、個々のd要素の中も回文になるはずなので、一見F(d) = K^ceil(d/2)である。
ただこれは周期がdよりも短いものを含んでいるので、d未満のdの約数d'について、F(d)からF(d')を順次引いていこう。

ここから回転させることを考える。

• dが奇数の場合、0～(d-1)要素回転させた場合の数列はすべてことなる(dは最小周期のため)
• dが偶数の場合、0～(d/2-1)要素回転させた場合の数列はすべてことなる。(d/2要素回転させるとまた別のd周期の回文になってしまう。)

よってdが奇数の場合d*F(d)、偶数の場合d/2*F(d)の和を足しこんでいけばよい。

ll N,K,M;
ll mo=1000000007;
vector<ll> V;
ll dp[2020];

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;
}

vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for(ll i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	return S;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	V=enumdiv(N);
	M=V.size();
	
	ll ret=0;
	FOR(x,M) {
		dp[x] = modpow(K,(V[x]+1)/2);
		FOR(y,x) if(V[x]%V[y]==0) dp[x] += mo - dp[y];
		dp[x] %= mo;
		
		if(V[x]%2==0) {
			ret += dp[x]*V[x]/2;
		}
		else {
			ret += dp[x]*V[x];
		}
	}
	cout<<ret%mo<<endl;
	
	
}

まとめ

うーん、下手にKUPC2016の数え上げが頭に残ってたせいでそれに引っ張られすぎた。