bzoj2160(manacher)

本文主要是介绍bzoj2160(manacher)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

manacher复习

可以按照自己思路来写

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=19930726;int n,m,p[1000005];
ll k,f[1000005];
char s[1000005];ll aa(ll a,ll b)
{ll ans=1;while (b){if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}int main()
{scanf("%d%lld",&n,&k);scanf("%s",s+1);s[0]='$';int id=0,mx=0;for (int i=1;i<=n;i++){if (mx>i) p[i]=min(mx-i,p[id-(i-id)]);else p[i]=0;while (s[i+p[i]]==s[i-p[i]]) p[i]++;p[i]--;if (i+p[i]>mx) mx=i+p[i],id=i;f[1+p[i]*2]++;}for (int i=n;i>=1;i--) f[i]+=f[i+2];ll ans=1;for (int i=n;i>=1&&k;i--) if (i&1) {ans=ans*aa(i,min(f[i],k))%mod;k-=min(f[i],k);}if (k) printf("-1");else printf("%lld",ans);return 0;
}

 

 

 

这篇关于bzoj2160(manacher)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---