ARC064 F - Rotated Palindromes

問題

以下の条件を全て満たす数列aを用意する
1) 長さn
2) 各要素は1以上k以下の整数
3) 回文(∴ aを逆順にした数列はaと一致する)
その後aを好きな回数rotateする
最終的なaとしてあり得るものは何通りか

1 <= n <= 10^9
1 <= k <= 10^9

解法

回文の条件があるから、rotateする前のaは手前半分を決めるともう半分は勝手に決まる
手前半分ってのは ceil(n/2) 文字
つまり最初のaとしては k^ceil(n/2) 通り考えられる
またそれぞれについて0〜n-1回rotateできるから、答えは単純に考えると計 n * k^m 個
ただしaが同じ数列を周期的に繰り返すようなときは、n回未満のrotateでaが元に戻るため、実際の答えはこんなに多くない
うまく重複を除く必要がある

最小でd回rotateすると元に戻るようなaは↑と同様に考えると k^ceil(d/2) 個存在する
またそれぞれについてrotate後のaがd通りあり得る
dの値はnの約数全通りあり得る
これらを踏まえて、包除原理の要領で
k^ceil(d/2) - Σ k^ceil(s/2)
(d: nの約数全て、s: dの約数でd以外のもの全て)
にdをかけたものを足し合わせていくと答えが求められる

ってのは嘘
rotate前のaが異なっていてもrotateによって同じ数列になるケースがある
つまり↑だとまだ足しすぎている
具体的にはdが偶数のときは「ある数列a」と「aをd/2回rotateした数列」で2重カウントしてしまう
(例えばn=8, d=4のとき、1221-1221と2112-2112なんかが重複する)
よってdが奇数のときは↑にdをかけたもの、偶数のときはd/2をかけたものを足し合わせていけばいい

ll n, k, num[2020], res;
vector<ll> d;

signed main() {
	cin >> n >> k;
	for (int i=1; i*i<=n; i++) if (n%i==0) {
		d.push_back(i);
		if (i*i!=n) d.push_back(n/i);
	}
	sort(all(d));
	rep(i,d.size()) {
		num[i] = mop(k, (d[i]+1)/2);
		rep(j,i) if (d[i]%d[j]==0) (num[i] += mod - num[j]) %= mod;
		(res += num[i] * d[i] / (d[i]%2 ? 1 : 2)) %= mod;
	}
	cout << res << endl;
}

https://beta.atcoder.jp/contests/arc064/tasks/arc064_d