洛谷1659 [国家集训队]拉拉队排练

Luogu

BZOJ

分析

$\mathrm{manacher}$ 。

先求出以每个数为中心的回文串长度。因为只关心奇数长度的串,所以没必要补#

然后考虑怎么统计答案。

设 $o[i]$ 表示长度为 $i$ 的回文串的个数。因为长度为 $i$ 的回文串包含了长度为 $j\;(j<i)$ 的回文串,所以可以先把每个长度加进去,再求一遍后缀和。

算答案就很简单,直接扫一遍,然后用快速幂计算就行了。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

const int N=1000000+10;
const int mod=19930726;

int n; ll k;
char s[N];
int f[N]; ll o[N];

inline void manacher() {
    int mid,maxright=0;
    for (re int i=0;i<n;++i) {
        if (i<maxright) f[i]=min(f[mid*2-i],f[mid]+mid-i);
        else f[i]=1;
        while (i-f[i]>=0&&i+f[i]<n&&s[i+f[i]]==s[i-f[i]]) ++f[i];
        if (i+f[i]>maxright) maxright=i+f[i],mid=i;
    }
}

inline int qpow(int a,ll b) {
    int ans=1;
    for (;b;b>>=1ll,a=1ll*a*a%mod)
        if (b&1ll) ans=1ll*ans*a%mod;
    return ans;
}

int main() {
    scanf("%d%lld",&n,&k); scanf("%s",s);
    manacher();
    for (re int i=0;i<n;++i) ++o[f[i]*2-1];
    for (re int i=n;i;--i) o[i]+=o[i+1];
    int ans=1;
    for (re int i=n;i;--i) {
        if (i&1) {
            if (o[i]>=k) { ans=1ll*ans*qpow(i,k)%mod,k=0; break; }
            k-=o[i],ans=1ll*ans*qpow(i,o[i])%mod;
        }
    }
    if (k) puts("-1");
    else printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 38 PM

发表评论