Codeforces 932G Palindrome Partition 回文树+DP

时间：2022-07-27 12:59:25

题意：给定一个串，把串分为偶数段

假设分为\(s_1,s_2,s_3....s_k\)

求满足$ s_1=s_k,s_2=s_{ k-1 }... $的方案数模\(10^9+7\)

\(|S|\leq 10^6\)

首先想到将原串变为\(s_1 s_n s_2 s_{n-2}...\) 这样问题变成了求将新串分成任意个偶数长度回文串的方案数

对于这个问题,我们先给出两个结论

\(1.\)一个回文串S的后缀\(T\)如果是回文串等价于\(T\)是\(S\)的$border $

\(2.\)将一个串\(S\)的所有\(borde\)r按长度从小到大排序后，能形成\(log\)个等差数列

设\(f_i\)表示\(s[1...i]\)分成回文串的方案数,\(g_p\)表示回文串\(p\)在\(s[1...i]\)中最后一次出现且此时为等差数列\((str_1,str_2,str_3...,p)\)的最后一项时的\(\sum_{str_i}f_{i-|str_i|}\)

对于一个等差序列,设当前节点为末项的等差数列有\(b_1,b_2,b_3\),公差为\(d\),其中\(|b1|>|b2|>|b3|\)那么有\(g_p=f_{i-b1}+f_{i-b2}+f_{i-b3}\)

根据结论\(1\),不难发现\(S_{i-b2,i-d}=S_{i-b3,i},S_{i-b1,i-d}=S_{i-b2,i}\),那么在\(g_{fail[p]}\)中就已经包含了\(f_{i-b1}\)和\(f{i-b2}\),只要把\(f_{i-b3}\)加上就好了

#include<bits/stdc++.h>

using namespace std;

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define pa pair<int,int>

#define mod 1000000007

#define ll long long

#define mk make_pair

#define pb push_back

#define lb double

#define fi first

#define se second

#define cl(x) memset(x,0,sizeof x)

#ifdef Devil_Gary

#define bug(x) cout<<(#x)<<" "<<(x)<<endl

#define debug(...) fprintf(stderr, __VA_ARGS__)

#else

#define bug(x)

#define debug(...)

#endif

const int INF = 0x7fffffff;

const int N=1e6+5;

/*

char *TT,*mo,but[(1<<15)+2];

#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/

inline int read(){

    int x=0,rev=0,ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return rev?-x:x;

}

int n,lst,cnt=1,id[N],nxt[N],c[N][26],fail[N],len[N],f[N],g[N],diff[N];

char s[N],ss[N];

int extend(int x,int n){

	int p=lst;

	while(s[n-len[p]-1]!=s[n]) p=fail[p];

	if(!c[p][x]){

		int now=++cnt,k=fail[p];

		len[now]=len[p]+2;

		while(s[n-len[k]-1]!=s[n]) k=fail[k];

		fail[now]=c[k][x],c[p][x]=now;

		diff[now]=len[now]-len[fail[now]];

		if(diff[now]==diff[fail[now]]) nxt[now]=nxt[fail[now]];

		else nxt[now]=fail[now];

	}

	return lst=c[p][x];

}

int main(){

#ifdef Devil_Gary

	freopen("in.txt","r",stdin);

#endif

	scanf("%s",ss+1),n=strlen(ss+1);

	for(int i=1,j=0;i<=n;i+=2) s[i]=ss[++j];

	for(int i=2,j=n+1;i<=n;i+=2) s[i]=ss[--j];

	fail[0]=fail[1]=1,len[1]=-1,f[0]=1;

	for(int i=1;i<=n;i++) id[i]=extend(s[i]-'a',i);

	for(int i=1;i<=n;i++){

		for(int j=id[i];j;j=nxt[j]){

			g[j]=f[i-len[nxt[j]]-diff[j]];

			if(diff[j]==diff[fail[j]]) (g[j]+=g[fail[j]])%=mod;

			if(!(i&1)) (f[i]+=g[j])%=mod;

		}

	}

	printf("%d\n",f[n]);

}

相关文章