[SDOI2018]反回文串

题意

问有多少个长度为\(N\)且字符集大小为\(K\)的字符串可以通过回文串旋转（把第一个字符移到最后）若干次得到。\(K\le N≤10^{18}\)

做法

ARC64F的加强版

设\(h(d)=d~is~odd?d:\frac{d}{2}\)，\(f(d)\)为最小周期为\(i\)的回文串
有\(g(d)=K^{\left\lceil\frac{d}{2}\right\rceil}=\sum\limits_{i|d}f(i)\)
反演一下有：\(f(n)=\sum\limits_{d|n}\mu(d)g(\frac{n}{d})\)
有：\[\begin{aligned}\\
Ans&=\sum\limits_{d|n}h(d)\sum\limits_{p|d}\mu(p)g(\frac{d}{p})\\
&=\sum\limits_{p|n}g(p)\sum\limits_{d|\frac{n}{p}}h(dp)\mu(d) \\
\end{aligned}\]

在大多数情况下有，\(h(dp)=dh(p)\)
在不满足条件：\(d~is~even,p~is~odd\)时，容易得出\(\frac{n}{p}~is~even,\sum\limits_{d|\frac{n}{p}}h(dp)\mu(d)=0\)，故在不考虑这部分的情况下：\[\begin{aligned}\\
\sum\limits_{d|\frac{n}{p}}h(dp)\mu(d)&=h(p)\sum\limits_{d|\frac{n}{p}}\mu(d)d \\
&=h(p)\prod\limits_{i=1}^k (1-p_i)~~~(\frac{n}{p}=\prod\limits_{i=1}^k p_i^{deg_i})\\
\end{aligned}\]

用Pollard-Rho分解质因数然后dfs即可
\(O(Pollard-Rho(N)+\sigma_0(N)logN)\)

巴特西

[SDOI2018]反回文串

题意

做法

最新文章

热门文章