[SDOI2018]反回文串

题意

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

做法

ARC64F的加强版

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

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

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

[SDOI2018]反回文串

原文：https://www.cnblogs.com/Grice/p/12370789.html