[ BZOJ 2160 ] 拉拉隊排練

\(\\\)

\(Description\)

---

一個由小寫字母構成的長為\(N\)的字符串，求前\(K\)長的奇數長度回文子串長度之積，對\(19930726\)取模后的答案。

• \(N\in [1,10^6]\)，\(K\in [1,10^{12}]\)

\(\\\)

\(Solution\)

---

• \(Manacher\)處理出所有位置的回文半徑，因為答案要求奇數長度，所以不用插入特殊字符，在原串上直接跑\(Manacher\)就好，回文半徑內的以當前點為回文中心的每一個子串都是回文串。
• 所以開一個長度的桶，只給回文半徑對應的最長子串長度打標記，顯然一個標記代表著后面所有位置都\(+1\)，所以計算的時候，一個長度的回文子串個數是長度標記的前綴和。
• 要求的\(K\)非常大，快速冪處理。

\(\\\)

\(Code\)

---

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000010
#define R register
#define gc getchar
#define mod 19930726
using namespace std;
typedef long long ll;char c,s[N];ll m,res=1,sum;int n,len[N],cnt[N];inline void init(){scanf("%d%lld",&n,&m);while(!isalpha(c=gc()));s[1]=c; s[0]='['; s[n+1]=']';for(R int i=2;i<=n;++i) s[i]=gc();
}inline void manacher(){for(R int i=1,p=0,mr=0;i<=n;++i){len[i]=i>mr?1:min(mr-i+1,len[(p<<1)-i]);while(s[i-len[i]]==s[i+len[i]]) ++len[i];if(i+len[i]-1>mr){p=i;mr=i+len[i]-1;}++cnt[(len[i]<<1)-1];}
}inline ll qpow(ll x,ll t){ll res=1;while(t){if(t&1) (res*=x)%=mod;(x*=x)%=mod; t>>=1;}return res;
}int main(){init();manacher();for(R int i=((n/2)<<1)+1;i>=1;i-=2){sum+=(ll)cnt[i];if(sum>=m){printf("%lld",(res*qpow(i,m))%mod);return 0;}(res*=qpow(i,sum))%=mod; m-=sum;}puts("-1");return 0;
}