Rotated Palindromes
题目链接:luogu AT2155
题目大意
问你有多少个长度为 n 的数组满足你可以通过不断的把第一个数放到最后一个位置上,使得这个数组变成一个回文串。
思路
首先想到一个显然错误的东西:
直接考虑先正常一个回文串 \((\frac{n+1}{2})^k\),然后它会有 \(n\) 种移位,但因为会重复所以显然是错的。
那你就要考虑怎么不重复的求,不难想到一个东西:最小循环节。
那假设我们已经知道有多少个回文串的最小循环节是 \(x\),你要怎么求它的贡献(毕竟它是可以移位的)
分奇偶讨论,如果是奇数,那显然它那个中间的位置是特别的,所以要循环 \(x\) 次才会得到一个重复的。
如果是偶数,那你会想到它循环 \(x/2\) 此就会有重复的了(\(abba\rightarrow baab\))。
那你接着问题就是求有多少个的最小循环节是 \(x\)。
这个考虑容斥 DP,就先是循环节有 \(x\) 的:\((\frac{x+1}{2})^k\)。
然后你枚举它的因子,它们作为最小循环节都不可以,所以要减去它们。
然后就求出来了,答案根据奇偶分别贡献也有了。
代码
#include<cstdio>
#include<algorithm>
#define ll long long
#define mo 1000000007
using namespace std;
int n, k, a[100001];
ll f[100001], ans;
ll ksm(ll x, ll y) {
ll re = 1;
while (y) {
if (y & 1) re = re * x % mo;
x = x * x % mo; y >>= 1;
}
return re;
}
int main() {
scanf("%d %d", &n, &k);
for (int i = 1; i * i <= n; i++)
if (n % i == 0) {
a[++a[0]] = i; if (i * i != n) a[++a[0]] = n / i;
}
sort(a + 1, a + a[0] + 1);
for (int i = 1; i <= a[0]; i++) {
f[i] = ksm(k, (a[i] + 1) / 2);
for (int j = 0; j < i; j++)
if (a[i] % a[j] == 0)
f[i] = (f[i] - f[j] + mo) % mo;
if (a[i] & 1) ans = (ans + f[i] * a[i] % mo) % mo;
else ans = (ans + f[i] * a[i] / 2 % mo) % mo;
}
printf("%lld", ans);
return 0;
}