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

用 Manacher 跑出回文串长，注意这里不需要偶数长度所以不需要对串做一些奇怪的处理

然后用前缀和搞一下，计算答案时跑快速幂即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define ll long long

namespace man {

const int N = 1100005;

char str[N], s[N<<1];

int a[N<<1];

int manacher(int len){

    a[0] = 0;

    int ans = 0, j;

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

        while(i-a[i]>0 && s[i+a[i]+1]==s[i-a[i]-1]) a[i]++;

        if(ans < a[i])ans = a[i];

        j = i+1;

        while(j<=i+a[i] && i-a[i]!=i+i-j-a[i+i-j]){

            a[j] = min(a[i+i-j], i+a[i]-j);

            j++;

        }

        a[j] = max(i+a[i]-j, 0ll);

        i = j;

    }

    return ans;

}

int solve(){

    int len;

    len = strlen(str);

    for(int i=0;i<len;i++) s[i]=str[i];

    return manacher(len);

}

}

const int N = 1000005;

const int modulo = 19930726;

int qpow(int p,int q) {

    ll r = 1;

    for(; q; p*=p, p%=modulo, q>>=1) if(q&1) r*=p, r%=modulo;

    return r;

}

int n,k,a[N];

signed main() {

    scanf("%lld%lld%s",&n,&k,man::str);

    man::solve();

    for(int i=0;i<n;i++) {

        a[man::a[i]]++;

    }

    for(int i=N-2;i>=0;--i) a[i]+=a[i+1];

    int ans=1;

    for(int i=N-2;i>=0;--i) {

        ans*=qpow(i*2+1,min(a[i],k));

        ans%=modulo;

        k-=min(a[i],k);

    }

    cout<<ans;

}

巴特西

[国家集训队] 拉拉队排练 - Manacher

最新文章

热门文章