傻逼题……manacher求出每个长度的极长回文串都有多少个，然后把长度相等的快速幂一起乘，然后把长度-2
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<iomanip> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<bitset> using namespace std; #define MAXN 2000010 #define MAXM 1010 #define ll long long #define INF 1000000000 #define MOD 19930726 #define eps 1e-8 char s[MAXN]; int n; ll k; int f[MAXN],mx,now; int v[MAXN]; ll ans; ll mi(ll x,ll y){ ll re=1; while(y){ if(y&1){ (re*=x)%=MOD; } (x*=x)%=MOD; y>>=1; } return re; } int main(){ int i; scanf("%d%lld",&n,&k); scanf("%s",s+1); for(i=n;i;i--){ s[i<<1]=s[i]; s[i<<1|1]='*'; } s[1]='*'; s[0]='$'; n=n<<1|1; for(i=1;i<=n;i++){ if(i<=mx){ f[i]=min(f[now*2-i],mx-i); } for(;s[i+f[i]+1]==s[i-f[i]-1];f[i]++){ } if(i+f[i]>mx){ mx=i+f[i]; now=i; } } for(i=2;i<=n;i+=2){ f[i>>1]=f[i]; } n>>=1; for(i=1;i<=n;i++){ v[f[i]]++; } ans=1; for(i=n;i;i--){ (ans*=mi(i,min((ll)v[i],k)))%=MOD; k-=v[i]; if(i!=1){ v[i-2]+=v[i]; } if(k<=0){ break; } } printf("%lld\n",ans); return 0; } /* */