BZOJ2160: 拉拉队排练【manacher】

2160: 拉拉队排练

【题目描述】

传送门

【题解】

如果当前回文长度为K,那么这个回文串K-2,K-4,K-6…肯定也有贡献,我们可以记住长度为i的回文个数,然后快速幂求就可以了。
好像不用判-1,判了就WA了。

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN=1000005,MOD=19930726;
int n,p[MAXN<<1],hsh[MAXN<<1];
char ch[MAXN],s[MAXN<<1];
LL K,Ans=1;
void manacher(){
    int pos=0,R=0;
    for(int i=1;i<=n;i++){
        if(i<R) p[i]=min(p[2*pos-i],R-i);else p[i]=1;
        while(i-p[i]>=1&&i+p[i]<=n&&s[i-p[i]]==s[i+p[i]]) p[i]++;
        if(i+p[i]>R) R=i+p[i],pos=i;
    }
}
LL qsm(LL x,int y){
    LL Sum=1;
    for(;y;y>>=1,x=x*x%MOD) if(y&1) Sum=Sum*x%MOD;
    return Sum;
}
int main(){
    scanf("%d%lld%s",&n,&K,ch+1);
    for(int i=1;i<=n;i++) s[i<<1]=ch[i],s[(i<<1)-1]='%';
    s[n<<1|1]='%';n=n<<1|1;manacher();
    for(int i=1;i<=n;i++) if(s[i]!='%') hsh[(p[i]/2-1)*2+1]++;
    for(int i=n;i;i--){
        hsh[i]+=hsh[i+2];
        if(K-hsh[i]>=0) K-=hsh[i],Ans=Ans*qsm(i,hsh[i])%MOD;
        else{Ans=Ans*qsm(i,K)%MOD;break;}
    }
    printf("%lld\n",Ans);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部