題目鏈接

(BZOJ) https://www.lydsy.com/JudgeOnline/problem.php?id=5330
(Luogu) https://www.luogu.org/problem/P4607

題解

首先觀察一些性質。
一個回文串可以輪換產生多少個本質不同的串？周期那么多個。
可是有一種特殊情況，就是對于長度為偶數的回文串\(a=ss^Rss^Rss^R...ss^R\) (\(s^R\)表示\(s\)的reverse), 如果輪換位數恰好等于周期的一半，那么會產生\(a'=s^Rss^Rss^Rs...s^Rs\), 這是另一個回文串，因此會算重！
于是我們大膽猜測，設\(a\)的周期為\(T\), 則當\(T\)為偶數時對答案的貢獻為\(\frac{T}{2}\), 否則為\(T\).
一個簡單的證明是，串\(a\)輪換\(d\)位和輪換\(T-d\)位所得到的串互為reverse，若得到了回文串，那么\(d=T-d\).

那么現在我們的問題簡化了: 設長度為\(n\)字符集為\(m\)周期為\(T\)的回文串有\(g(T)\)個，要求的就是\(\sum_{d|n}g(d)h(d)\), 其中\(h(d)\)為貢獻。
現在考慮怎么算周期為\(T\)的回文串: 設\(G(T)\)表示有多少個回文串滿足\(T\)是它的周期(但不是最小周期，即周期是\(T\)的因數)，則\(G(T)=m^{\lceil \frac{T}{2}\rceil}\).
且有\(G(T)=\sum_{d|T}g(d)\), 由莫比烏斯反演可得\(g(T)=sum_{d|T}\mu(\frac{T}ze8trgl8bvbq)G(d)\).
然后直接枚舉因數裸求就可以得到54至60分(當然也可以\(g(T)=G(T)-\sum_{d|T}g(d)\), 但是這樣由于復雜度較劣只有30至36分，期望得分是官方題解里給的)

當\(n\le 10^{18}\)時，\(n\)的約數個數\(d(n)\le 103680\).
推式子: \(\sum_{d|n}\sum_{d'|d}G(d')\mu(\fracze8trgl8bvbq{d'})h(d)=\sum_{d|n}\sum_{d'|\frac{n}ze8trgl8bvbq}G(d)\mu(d')h(dd')\)
觀察式子，當\(d\)為奇數\(\frac{n}ze8trgl8bvbq\)為偶數時，每一個奇數都會和一個偶數配成一對，并且\(\mu\)值相反。因此這種情況對答案貢獻為\(0\).
在其他情況下，一定滿足\(h(dd')=h(d)d'\), 即\(\sum_{d|n}G(d)h(d)\sum_{d'|\frac{n}ze8trgl8bvbq}d'\mu(d')\)
考慮\(\sum_{d|n}d\mu(d)\)的組合意義，易得原式等于\(\sum_{d|n}G(d)h(d)\prod_{p|\frac{n}ze8trgl8bvbq}(1-p)\), 其中\(p\)為質數
DFS所有的質因數即可。

時間復雜度\(O(n^{\frac{1}{4}}\log n+d(n)\log n)\), 其中\(d(n)\)為\(n\)的約數個數.

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<algorithm> #include<vector> #define llong long long #define pll pair<llong,llong> #define mkpr make_pair using namespace std;const int N = 103680; vector<pll> pfac; llong P;llong quickmul(llong x,llong y,llong mod=P) {return (x%mod)*(y%mod)%mod; } llong quickpow(llong x,llong y,llong mod=P) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {ret = quickmul(ret,cur,mod)%mod; y-=(1ll<<i);}cur = quickmul(cur,cur,mod);}return ret; }namespace Pollard_Rho {const int N = 15;const int LGM = 64;llong fc[LGM+2];llong a[N+2];llong m;int n;llong ans;llong quickmul(llong x,llong y,llong mod=P){llong tmp=(x*y-(llong)((long double)x/mod*y+1.0e-8)*mod)%mod;return tmp<0 ? tmp+mod : tmp;}llong quickpow(llong x,llong y,llong mod=P){llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {ret = quickmul(ret,cur,mod)%mod; y-=(1ll<<i);}cur = quickmul(cur,cur,mod);}return ret;}llong gcd(llong x,llong y) {return y==0 ? x : gcd(y,x%y);}llong absl(llong x) {return x>=0 ? x : -x;}llong ssrand(llong x,llong c,llong y) {return (quickmul(x,x,y)+c)%y;}bool Miller_Rabin(llong x){if(x==1) return false;if(x==2) return true;if((x&1)==0) return false;llong y = x-1,t = 0ll;while((y&1)==0) y>>=1,t++;for(int i=1; i<=5; i++){llong bas = rand()%(x-1)+1;llong cur = quickpow(bas,y,x);for(int j=1; j<=t; j++){llong tmp = quickmul(cur,cur,x);if(tmp==1 && cur!=1 && cur!=x-1) return false;cur = tmp;}if(cur!=1) return false;}return true;}llong pollard_rho(llong x,llong c){llong i = 1,k = 2;llong y = rand()%(x-1)+1; llong t = y;while(true){i++;y = ssrand(y,c,x);llong d = gcd(absl(t-y),x);if(d>1 && d<x) return d;if(t==y) return x;if(i==k){t = y;k<<=1;}}}void factorize(llong x,llong c){if(x==1) return;if(Miller_Rabin(x)){n++; fc[n] = x;return;}llong p = x,k = c;while(p>=x) p = pollard_rho(p,c--);factorize(p,k); factorize(x/p,k);}void Factorize(llong _m){m = _m;n = 0;factorize(m,120);sort(fc+1,fc+n+1);pfac.clear();for(int i=1; i<=n; i++){if(fc[i]==fc[i-1]) {pfac[pfac.size()-1].second++;}else {pfac.push_back(mkpr(fc[i],1));}}} }llong n,m; llong ans;void dfs(int pos,llong x,llong coe) {if(pos==pfac.size()){if((x&1ll) && (!((n/x)&1ll))) {return;}llong tmp = quickmul(coe,quickmul(quickpow(m,(x+1)>>1),(x&1)?x:(x>>1)));ans = (ans+tmp)%P;return;}for(int i=0; i<=pfac[pos].second; i++){dfs(pos+1,x,i==pfac[pos].second?coe:quickmul(coe,(P+1-pfac[pos].first%P)));x = x*pfac[pos].first;} }int main() {srand(time(NULL));int T; scanf("%d",&T);while(T--){scanf("%lld%lld%lld",&n,&m,&P);Pollard_Rho::Factorize(n); // for(int i=0; i<pfac.size(); i++) printf("(%lld,%lld) ",pfac[i].first,pfac[i].second); puts("");ans = 0ll;dfs(0,1ll,1ll);printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 5330 Luogu P4607 [SDOI2018]反回文串 (莫比乌斯反演、Pollard Rho算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。