目录
BZOJ2160 拉拉队排练题解ｃｏｄｅ
BZOJ2160 拉拉队排练
题目传送门
题解
比较裸的回文自动机题目。构建出回文自动机之后，就可以把所有回文子串的长度记录下来，然后\(sort\)一下，选出前\(K\)个，然后快速幂计算答案就行了。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=1e6+500;
const int Md=19930726;
int n;
ll k;
char s[maxn];
typedef pair<int,int>P;
P S[maxn];
#define fi first
#define se second
ll res=1;
/*==================Define Area================*/
struct pldTree {
struct node {
int son[26];
int len,fail;
}t[maxn];
int sz[maxn];
int last,tot;
void init() {
t[0].fail=t[1].fail=1;
t[tot=1].len=-1;
}
void insert(int c,int n,char *s) {
int p=last;
while(s[n-t[p].len-1]!=s[n]) p=t[p].fail;
if(!t[p].son[c]) {
int o=++tot,k=t[p].fail;
t[o].len=t[p].len+2;
while(s[n-t[k].len-1]!=s[n]) k=t[k].fail;
t[o].fail=t[k].son[c];
t[p].son[c]=o;
}
sz[last=t[p].son[c]]++;
}
void Cal() {
for(int i=tot;i;i--) {
sz[t[i].fail]+=sz[i];
}
}
}T;
ll Powe(ll x,ll y) {
ll res=1;
while(y) {
if(y&1) res=1ll*res*x%Md;
x=1ll*x*x%Md;
y>>=1;
}
return res%Md;
}
int main() {
read(n);read(k);
scanf("%s",s+1);
T.init();
for(int i=1;i<=n;i++) T.insert(s[i]-'a',i,s);
T.Cal();
for(int i=2;i<=T.tot;i++) {
S[i-1]=P(-T.t[i].len,T.sz[i]);
}
int tt=T.tot-1;
sort(S+1,S+1+tt);
for(int i=1;i<=tt;i++) {
S[i].fi=-S[i].fi;
if(!(S[i].fi&1)) continue;
ll c=min(k,1ll*S[i].se);
// printf("c:%lld\n",c);
ll ret=Powe(1ll*S[i].fi,c);
res=1ll*res*ret%Md;
k-=c;
}
if(!k) printf("%lld\n",res);
else puts("-1");
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9430934.html
相关资源：数据结构—成绩单生成器
