1 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5,mod=1e9+7; int n,sz,lst,ch[N][26],c[N],fa[N],df[N],to[N],len[N],pos[N]; ll f[N],g[N]; string a,b; void ins(int c,int x) { auto find=[&](int p,int x){while(a[x]!=a[x-len[p]-1])p=fa[p];return p;}; int p=find(lst,x); if(!ch[p][c]) { fa[++sz]=max(1,ch[find(fa[p],x)][c]),ch[p][c]=sz,len[sz]=len[p]+2,df[sz]=len[sz]-len[fa[sz]]; if(df[sz]!=df[fa[sz]])to[sz]=sz;else to[sz]=to[fa[sz]]; }lst=ch[p][c]; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>b,n=b.size(),b=' '+b,len[0]=-1,sz=lst=1,a.resize(n+1); for(int i=1;i<=n/2;i++)a[i*2-1]=b[i],a[i*2]=b[n-i+1]; f[0]=1; for(int i=1;i<=n;i++) { ins(a[i]-'a',i); for(int x=lst;x;x=fa[to[x]]) { g[x]=(f[i-len[to[x]]]+(to[x]!=x)*g[fa[x]])%mod; if(i%2==0)f[i]=(f[i]+g[x])%mod; } }cout<<f[n]<<'\n'; return 0; }
- 1
信息
- ID
- 6875
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者