反回文串[SDOI2018]

发表于 分类于

题目链接

luogu

loj

题意

求字符集大小为 $k$ 的，长度为 $n$ 的所有字符串，满足存在至少一种旋转同构的情况，使得旋转后该串为回文串。

$k\leq n\leq 10^{18}$

题解

假设我们先枚举回文串，然后计算这个回文串有多少种情况。这个方案数相当于就是，你一直将这个回文串旋转，直到变成了另外一个回文串，此时旋转的次数就是方案数。

可以发现，对于一个回文串，这旋转的次数和它最小的循环节有关（此处的循环节指倍长后相等）。

如果最小的循环节 $d$ 是偶数，那么旋转的次数为 $\frac{d}{2}$，否则旋转的次数为 $d$。

那么试着枚举这个 $d$。设 $f(d)$ 表示长度为 $n$，字符集大小为 $k$，最小循环节的长度为 $d$ 的回文串个数，设 $g(n)=k^{\lceil \frac{n}{2}\rceil}$ 表示长度为 $n$，字符集大小为 $k$ 的回文串个数。

显然有：$\sum_{d|n}f(d)=g(n)$。

莫比乌斯反演：$\sum_{d|n}\mu(\frac{n}{d})g(d)=f(n)$

设 $h(d)$ 为当循环节为 $d$ 时的旋转次数，即 $h(d)=\frac{d}{1+[2|d]}$。

那么最终答案就是：

$$\sum_{d|n}f(d)h(d)\=\sum_{d|n}h(d)\sum_{m|d}\mu(\frac{d}{m})g(m)\=\sum_{m|n}g(m)\sum_{d|\frac{n}{m}}\mu(d)h(dm)$$

下面来看看 $W(k,m)=\sum_{d|k}\mu(d)h(dm)$ 怎样求？

可以发现，当 $m$ 为奇数，$k$ 为偶数的时候，$W(k,m)=0$。

其他情况，则有：$W(k,m)=h(m)\sum_{d|k}\mu(d)d$

那么答案就是：$\sum_{m|n}g(m)h(m)[m\equiv 1& \frac{n}{m}\equiv 0]\sum_{d|\frac{n}{m}}\mu(d)d$

然后再来看看 $\sum_{d|k}\mu(d)d$ 怎么求。

显然只需要考虑 $\mu(d)\not =0$ 的项。那么就是枚举哪个质因子选不选，即 $\prod_{p\in \mathbb{P},p|k}(1-p)$。

剩下的就用pollard_rho分解下质因数，然后枚举 $\frac{n}{m}$ 即可。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second

ll mod;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll mul(ll x,ll y,ll n)
{
    return (x*y-(ll)((lb)x*y/n)*n+n)%n;
}
inline ll Pow(ll x,ll y,ll p=mod)
{
   ll ans=1;for(;y;y>>=1,x=mul(x,x,p)) if(y&1) ans=mul(ans,x,p);
   return ans;
}

vector<ll> d;

namespace PollardRho{
    const int prime[7]={2,3,5,11,61,31,29};
    const int m=7;
    int t; ll r;
    inline bool witness(int a,ll n)
    {
        ll b=Pow(a,r,n);
        if(b==1) return 1;
        for(int i=0;i<t;i++,b=mul(b,b,n)) if(b==n-1) return 1;
        return 0;
    }
    inline bool isprime(ll n)
    {
        if(n==1) return 0;
        ff(i,0,m)
        {
            if(n==prime[i]) return 1;
            if(n%prime[i]==0) return 0;
        }
        r=n-1;
        for(t=0;!(r&1);r>>=1) t++;
        ff(i,0,m) if(!witness(prime[i],n)) return 0;
        return 1;
    }
    inline ll pollard_rho(ll n)
    {
        ll c=rand()%(n-1),x=rand()%n,y=x,d;
        for(int i=1,k=2;i++;)
        {
            x=(mul(x,x,n)+c)%n;
            d=__gcd(abs(y-x),n);
            if(d!=1&&d!=n) return d;
            if(y==x) return n;
            if(i==k) y=x,k<<=1;
        }
    }

    void find(ll n)
    {
        if(n==1) return;
        if(isprime(n)) return (void)(d.pb(n));
        ll x=n; for(;x==n;x=pollard_rho(n));
        find(x); find(n/x);
    }
}
using PollardRho::find;

ll n,k,ans;
int m,cnt,t[100];
ll po[100][100];

void dfs(int u,ll d,ll s)
{
    if(u>cnt)
    {
        if((d&1)==0&&((n/d)&1)) return;
        ll nd=n/d;
        ans=Add(ans,Pow(k,(nd+1)/2)*(((nd&1ll)?nd:(nd/2))%mod)%mod*((s%mod+mod)%mod)%mod);
        return;
    }
    dfs(u+1,d,s);
    fo(i,1,t[u]) dfs(u+1,d*po[u][i],s*(1ll-po[u][1]));
}

int main()
{
    int T;scanf("%d",&T);
    for(;T--;)
    {
        cin>>n>>k>>mod;
        k%=mod;
        d.clear();
        find(n);
        sort(all(d));
        //for(auto v:d) DEBUG(v);
        m=d.size(); cnt=0;
        for(int i=0,j;i<m;i=j)
        {
            po[++cnt][0]=1;
            po[cnt][1]=d[i];
            for(j=i+1;j<m;j++)
                if(d[j]!=d[i]) break;
                else po[cnt][j-i+1]=po[cnt][j-i]*d[i];
            t[cnt]=j-i;
        }
        ans=0;
        dfs(1,1,1);
        printf("%lld\n",ans);
    }
    return 0;
}