[??记录]AT2155 [ARC064D] Rotated Palindromes
command_block
2021-05-01 13:07:00
**题意** ： 首先生成一个长度为 $n$ ，字符集为 $[1,k]∩Z$ 的回文串 $A$。
然后，进行任意次以下操作：
- 把 $a$ 中的第一个元素移到最后。
经过这些步骤，一共可以得到多少种不同的数列 $a$ 呢？答案对 $10^9+7$ 取模。
$n,k\leq 10^9$ ，时限$\texttt{2s}$。
------------
我们发现，操作等价于进行循环移位。
考察回文串与循环移位之间的映射。
一个最小整周期为 $c$ 的回文串 $s$ 能对应 $c$ 个本质不同的循环移位后的串 $t$。
再考虑反映射，我们发现，当 $c$ 为奇数时，一个 $t$ 只会对应一个 $s$ ，当 $c$ 为偶数时，一个 $t$ 恰好会对应两个 $s$。
如 $\texttt{abba,baab}$ 的最小整周期都是 $4$ ，它们对应的 $t$ 是相同的。
（另一种思路是，发现两个 $s$ 对应的 $t$ 要么完全相同，要么无交集。故只需要统计循环移位下本质不同的 $s$ 的个数，容易发现 $c$ 为偶数时等价类大小总是 $2$ ，为奇数时则总是 $1$）
于是，枚举 $c$ 计算答案 :
$${\rm Ans}=\sum\limits_{c|n}cf(c)*\begin{cases}1&(c\bmod 2=1)\\1/2&(c\bmod 2=0)\end{cases}$$
其中 $f(c)$ 是最小整周期为 $c$ 的回文串个数。
一个长度为 $c$ 的回文串方案数为 $k^{\lceil n/2\rceil}$ ，但如此随意生成的回文串可能有更小的整周期（是长度的因数）。
考虑莫比乌斯反演，设 $F(n)$ 为最小整周期是 $n$ 的因数的方案数。
则有 ：
$$
\begin{aligned}
F(n)&=k^{\lceil n/2\rceil}\\
F(n)&=\sum\limits_{d|n}f(d)\\
f(n)&=\sum\limits_{d|n}\mu(d)F(d)\\
\end{aligned}
$$
暴力计算，复杂度为 $O\big(\sqrt{n}+d(n)^2\big)$ ，可以通过。
注意到 $\mu(d)$ 只在 $d$ 中无平方因子时有值，于是 $d$ 的枚举可以简化。
```cpp
#include<algorithm>
#include<cstdio>
using namespace std;
const int mod=1000000007,lim=32500,inv2=500000004;
int k,pw1[33000],pw2[33000];
int pwk(int n)
{return 1ll*pw2[n/lim]*pw1[n%lim]%mod;}
void Init()
{
pw1[0]=pw2[0]=1;
for (int i=1;i<=lim;i++)pw1[i]=1ll*pw1[i-1]*k%mod;
for (int i=1;i<=lim;i++)pw2[i]=1ll*pw2[i-1]*pw1[lim]%mod;
}
int p[20],c[20],tn,ans;
int t[100500],cnt[100500];
int calc(int n,int s0)
{
int ret=pwk((n+1)/2);
for (int s=s0;s;s=(s-1)&s0)
if (cnt[s]&1)ret=(ret-pwk((n/t[s]+1)/2))%mod;
else ret=(ret+pwk((n/t[s]+1)/2))%mod;
return ret;
}
void dfs(int i,int s,int d)
{
if (i==tn){
ans=(ans+1ll*(d&1 ? d : d/2)*calc(d,s))%mod;
return ;
}
dfs(i+1,s,d);
for (int j=1,buf=p[i];j<=c[i];j++,buf*=p[i])
dfs(i+1,s|(1<<i),1ll*d*buf);
}
int main()
{
int n;
scanf("%d%d",&n,&k);Init();
for (int i=2;i*i<=n;i++)
if (n%i==0){
p[tn]=i;
while(n%i==0)
{n/=i;c[tn]++;}
tn++;
}
if (n>1){p[tn]=n;c[tn++]=1;}
t[0]=1;
for (int i=0;i<tn;i++)
{t[1<<i]=p[i];cnt[1<<i]=1;}
for (int s=0;s<(1<<tn);s++)
{t[s]=t[s^(s&-s)]*t[s&-s];cnt[s]=cnt[s>>1]+(s&1);}
dfs(0,0,1);
printf("%d",(ans+mod)%mod);
return 0;
}
```