luogu_1659【题解】manacher 啦啦队排练

题面：https://www.luogu.org/problemnew/show/P1659

这个题有一个需要注意的地方。

打个比方。

一个和谐团体5有个人。也可以说是3个人。也可以说是1个人。

所以要重复计算。之前的答案之后还要继续算。

所以需要用快速幂，要不然T到飞起。

用桶把所有的长度的个数都存下来。

每次都是人数的这时候长度的个数和之前的长度的和次方。

具体见代码吧，语言说不清楚。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1100000,mod=19930726;
int n;
int p[maxn<<1],ton[maxn];
char da[maxn<<1],c[maxn];
ll k,ans=1;
inline ll qp(int a,int b){
    if(a==1) return 1;
    ll ret=1,aa=a;
    while(b){
        if(b&1) ret=(ret*aa)%mod;
        aa=(aa*aa)%mod;
        b>>=1;
    }
    return ret;
}

inline void man(){
    da[0]='~';
    da[1]='#';
    for(int i=1;i<=n;i++){
        da[(i<<1)-1]='#';
        da[(i<<1)]=c[i];
    }
    int cnt=(n<<1)+1,mid=0,rb=0;
    da[cnt]='#';
    for(int i=1;i<=cnt;i++){
        if(i<rb)
            p[i]=min(p[(mid<<1)-i],rb-i);
        else p[i]=1;
        while(i-p[i]>=1 && p[i]+i<=cnt && da[i-p[i]]==da[i+p[i]])
            p[i]++;
        if(p[i]+i>rb)
            rb=p[i]+i,mid=i;
        if((p[i]-1)%2) ton[p[i]-1]++; 
    }
}
int main(){
    int shu=0;
    scanf("%d%d",&n,&k);
    scanf("%s",c+1);
    man();
    for(int i=n;i>=1;i--){
        if(i%2==0) continue;
        shu+=ton[i];
        if(k>=shu){
            ans=(ans*qp(i,shu))%mod;
            k-=shu;
        }else{
            ans=(ans*qp(i,k))%mod;
            k-=shu;
            break;
        }
    }
    if(k>0) ans=-1;
    printf("%lld
",ans);
    // system("pause");
    return 0;
}