1 条题解

  • 0
    @ 2026-5-5 16:54:06
    #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
    上传者