luogu P1659 [国家集训队]拉拉队排练

时间：2021-08-22 18:39:24

唔。。。。话说好久没有发布题解了（手痒痒了

首先特别鸣谢lykkk大佬今天下午教我Manacher算法，甚是感谢

为了体现学习成果，写一篇蒟蒻版的题解（大佬勿喷

言归正传

题面——>在这儿

首先做这道题要掌握一个算法——Manacher算法

简要说他就是用来解决回文串相关问题的算法，并不高深

由题意可知，显然每一个和谐群体就是一个长度为奇数的回文串

用Manacher可以求每个位置的回文半径

因为我们只要求奇数个的回文串，那么显然我们不需要在字符串里添加一些无关字符

那么我们用Manacher求出以当前位置为中心的最长回文子串长度

所以我们就会在求的同时搞出最长的len

然后根据对称性可知也有长为len*2-1的回文子串，接着我们只需要统计一下就可以了

注意我们只要奇数个，去掉偶数个

因为数据范围过大，所以我们要Fast_Pow使得不会爆掉

那么。。。下面我们来看一下我优秀的代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int mod = ;

const int N = ;

char s[N],str[N*];

int p[N*],cnt[N];

int len,n;

ll ans=,k;

ll ksm(int x,int y) {//因为数据范围很大容易爆掉，所以就要Fast_Pow

    if(x==) return ;

    ll res=,base=x;

    while(y) {

        if(y&) res=(res*base)%mod;

        base=(base*base)%mod;

        y>>=;

    }

    return res;

}

void manacher() {//Manacher模板，详见洛谷P3805

    for(int i=; i<=len; i++) str[i*-]='%',str[i*]=s[i];

    str[len=len*+]='%';

    int id=,mx=;

    for(int i=; i<=len; i++) {

        if(i<mx) p[i]=min(p[id*-i],mx-i);

        else p[i]=;

        while(p[i]+i<=len && i-p[i]>= && str[i+p[i]]==str[i-p[i]]) p[i]++;

        if(p[i]+i>mx) id=i,mx=i+p[i];

        if((p[i]-)%) cnt[p[i]-]++;

    }

}

int main() {

    int sum=;

    cin>>n>>k>>s+;

    len=n;

    manacher();

    for(int i=n; i>=; --i) {//根据题意常规操作

        if(i%==) continue;

        sum+=cnt[i];

        if(k>=sum) {

            ans=(ans*ksm(i,sum))%mod;

            k-=sum;

        } else {

            ans=(ans*ksm(i,k))%mod;

            k-=sum;

            break;

        }

    }

    if(k>) ans=-;

    cout<<ans;

    return ;

}

完结，撒花！！

相关文章