bzoj 5330: [Sdoi2018]反回文串

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=5330

难题做不来。。跑了跑了
如果按照loj的数据范围，我已经爆0了
首先，朴素的想法就是暴力控制$n/2$位，然后乘个n
但是你会发现，会有很多重复
考虑怎么样不会有重复，我们对于每个串，不要加上n
我们加上一个数$x$，$x$是这个回文串在将前缀x个位丢到后面会变成回文串
容易发现，这样就没有重复了
考虑一个东西的$x$怎么算
猜了很多个与gcd有关的结论。。都被$ABBAABBA$搞自闭了。。
但其实这个结论并不和gcd有关。。于是我就爆0了
我们先找他的循环节，设其长度为$len$，如果$len$为偶数，那么$x$就是$len/2$，否则就是$len$，（这个结论怎么证呢？T_T）
我们设$len$和$x$的转化关系为$h(len)$
解决了这个，那么每个串的贡献就之和他的循环节有关了
设$f(i)$表示循环节为$i$的回文串有多少个，$g(n)$表示长度为n的回文串
不难得到$$\sum _{d|n}f(n)=g(n)$$
又是熟悉的配方反演一下可以得到
$$f(n)=\sum _{d|n}\mu (\frac{n}{d})g(d)$$
根据定义可以得到$$ans=\sum _{d|n}f(d)?h(d)$$
暴力把二式套进去，可以得到$$ans=\sum _{d|n}h(d)\sum _{k|d}g(k)\mu (\frac{d}{k})$$
按照化式子的套路，我们把k提到前面枚举$$ans=\sum _{k|n}g(k)\sum _{d|\frac{n}{k}}h(dk)\mu (d)$$
然后陷入僵局。。
根据题解，我们尝试发现一些规律
首先，看一下这个$h(dk)$能不能变成$d?h(k)$
如果可以的话，那么式子的前后就变得很可做的样子
发现，$h(dk)?=d?h(k)$的情况，当且仅当$dk$为偶数，且$k$为奇数
我们再来观察一下当满足这些条件的时候$$\sum _{d|\frac{n}{k}}h(dk)\mu (d)$$会变成什么
因为k是奇数，所以可以得到d是一个偶数，所以$\frac{n}{k}$也是偶数
根据题解我们不妨直接讨论一个更大的范围，就是讨论$k$为奇数$\frac{n}{k}$为偶数的情况
要注意，这里对dk并没有要求，我们讨论了一个更大的范围
我们发现，假如我们只考虑$\mu$不为0的情况
$d$含$2$和不含$2$的情况，刚好$\mu$为相反数，且$h(dk)$是一样的！
因此，我们可以跳过所有$k$为奇数$\frac{n}{k}$为偶数的情况，那么，$h(dk)$就可以提出来了
最后，式子变成了$$ans=\sum _{k|n}g(k)h(k)\sum _{d|\frac{n}{k}}d\mu (d)$$

最后一步，考虑后面的是什么。依然考虑$\mu$有值的情况，容易发现，这个东西就是$\Pi (1?p_i)$，其中$p_i$是$\frac{n}{k}$的质因数

于是问题就解决了，用rho来分解找因数即可

终于写完了
感觉这题还是很有启发的啊
1.猜循环节有关的结论不要死在gcd里面，有时暴力+1，-1，/2，*2可能会有奇效
2.一些式子看起来不好搞的时候，试一下可不可以换掉，换成一些可以求的。比如说这里的莫比乌斯反演
3.化$\mu$的时候还是要记住考虑$\mu$不为0的情况
4.有时候观察一下不可以化简的部分是否可以忽略掉

顺便学了一发更快的rho
有个细节就是最后dfs的时候快速幂没有必要用快速乘，只有rho的时候才要，否则你会T飞
但其实并没有关系，因为我也不会做

最后是CODE：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const LL N=105;
LL T;
LL pri[14]={
    0,2,3,5,7,11,13,17,19,23,29,31,37,41};
LL gcd (LL x,LL y)	{
    return x==0?y:gcd(y%x,x);}
LL mul (LL x,LL y,LL MOD)
{
    x%=MOD;LL lalal=0;while (y>0){
    if (y&1) lalal=(lalal+x)%MOD;x=x+x;if (x>=MOD) x-=MOD;y>>=1;}return lalal;
} 
LL Pow (LL x,LL y,LL MOD)
{
    x%=MOD;LL lalal=1;while (y>0){
    if (y&1) lalal=mul(lalal,x,MOD);x=mul(x,x,MOD);y>>=1;}return lalal;
}
vector<LL> vec;	
bool check (LL p)
{
    for (LL u=1;u<=13;u++){
    if (p==pri[u]) return true;if (p%pri[u]==0) return false; }LL k=0,t=p-1;while (t%2==0) {
    t>>=1;k++;}for (LL u=1;u<=13;u++){
    LL x=Pow(pri[u],t,p);for (LL i=0;i<k;i++){
    LL y=mul(x,x,p);if (y==1&&x!=1&&x!=p-1) return false;x=y;}if (x!=1) return false;}return true;
}
LL rho (LL n)
{
    LL c=rand()%(n-1)+1,x=rand()%n,y=x,p=1,k=1;for (LL u=1;p==1;u++){
    x=(mul(x,x,n)+c)%n;if (x==y) return n;p=gcd(n,x>y?x-y:y-x);if (u==k)	{
    y=x;k<<=1;}}return p;
}
void div (LL n)
{
    if (n==1) return ;if (check(n))	{
    vec.push_back(n);return ;}LL p=1;while (p==1) p=rho(n);div(p);div(n/p);
}
LL n,k,MOD;
LL a[N];
int b[N];
int tot;
LL ans;
LL H (LL x)	{
    return x&1?x%MOD:(x>>1)%MOD;}
LL Pow1 (LL x,LL y)
{
    x%=MOD;LL lalal=1;while (y>0){
    if (y&1) lalal=lalal*x%MOD;x=x*x%MOD;y>>=1;}return lalal;
}
void dfs (int now,LL d,LL xx)
{
    if (now>tot){
    LL nn=n/d;if (!(d&1)&&((nn)&1)) return ;ans+=Pow1(k,(nn+1)>>1)*H(nn)%MOD*xx%MOD;return ;}dfs(now+1,d,xx);xx=xx*(1-a[now])%MOD;for (int u=1;u<=b[now];u++)	{
    d=d*a[now];dfs(now+1,d,xx);}
}
int main()
{
    scanf("%lld",&T);while (T--){
    vec.clear();scanf("%lld%lld%lld",&n,&k,&MOD);k%=MOD;div(n);sort(vec.begin(),vec.end());int siz=vec.size();tot=0;for (int u=0;u<siz;u++){
    if (tot==0||vec[u]!=a[tot]) {
    a[++tot]=vec[u];b[tot]=1;}else b[tot]++;}ans=0;dfs(1,1,1);printf("%lld\n",(ans%MOD+MOD)%MOD);}return 0;
}