CF932G Palindrome Partition(回文自动机)

Luogu

题解时间

首先将字符串 $ s[1...n] $ 变成 $ s[1]s[n]s[2]s[n-1]... $

就变成了求将字符串全部划分为偶回文串的方案数。

建回文树大力跳$ fail $ 直接 $ dp $ 的复杂度是十分优秀的 $ O ( n ^ {2} ) $。

优化不容易想到。

考虑字符串上第 $ j $ 位为结尾的所有回文子串，毫无疑问它们在树上是一条链。

但它有个更重要的性质。

其中所有长度 $ > j / 2 $ 的子串的 $ len $ 等差。

证明有点难，但这个结论可能对做过[WC2016]论战捆竹竿的人来说十分熟悉。

然后将等差段的dp值整合到一起，每次跳就是 $ O( log_{2} n ) $。

然后就可以做了。

#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

struct pat{int x,y;pat(int x=0,int y=0):x(x),y(y){}bool operator<(const pat &p)const{return x==p.x?y<p.y:x<p.x;}};

template<typename TP>inline void read(TP &tar)

{

	TP ret=0,f=1;char ch=getchar();

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

	while(ch>='0'&&ch<='9'){ret=ret*10+(ch-'0');ch=getchar();}

	tar=ret*f;

}

namespace RKK

{

const int N=1000011,mo=1000000007;

void doadd(int &a,int b){if((a+=b)>=mo) a-=mo;}

int dlen[N],anc[N];

struct remilia{int tranc[26],len,fail;};

struct sakuya

{

	remilia p[N];

	int tcnt,fin;

	void init()

	{

		tcnt=fin=1;

		p[0].len=0,p[1].len=-1;

		p[0].fail=p[1].fail=1;

		anc[0]=1;

	}

	sakuya(){init();}

	int match(char *s,int i,int px){return s[i-p[px].len-1]==s[i];}

	void ins(char *s,int i)

	{

		int ch=s[i]-'a';

		int npx,lpx,lpy;

		lpx=fin;

		while(!match(s,i,lpx)) lpx=p[lpx].fail;

		if(!p[lpx].tranc[ch])

		{

			npx=++tcnt,p[npx].len=p[lpx].len+2;

			lpy=p[lpx].fail;

			while(!match(s,i,lpy)) lpy=p[lpy].fail;

			p[npx].fail=p[lpy].tranc[ch];

			p[lpx].tranc[ch]=npx;

			dlen[npx]=p[npx].len-p[p[npx].fail].len;

			anc[npx]=p[npx].fail;if(dlen[npx]==dlen[p[npx].fail]) anc[npx]=anc[p[npx].fail];

		}

		fin=p[lpx].tranc[ch];

	}

}pam;

int n;char str[N],rts[N];

int dp[N],dg[N];

int main()

{

	#ifdef RDEBUG

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

	#endif

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

	for(int i=1;i<=n>>1;i++) rts[(i<<1)-1]=str[i];

	reverse(str+1,str+1+n);

	for(int i=1;i<=n>>1;i++) rts[i<<1]=str[i];

	dg[0]=1;

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

	{

		pam.ins(rts,i);for(int px=pam.fin;px;px=anc[px])

		{

			dp[px]=dg[i-pam.p[anc[px]].len-dlen[px]];

			if(anc[px]!=pam.p[px].fail) doadd(dp[px],dp[pam.p[px].fail]);

			if((i&1)==0) doadd(dg[i],dp[px]);

		}

	}

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

	return 0;

}

}

int main(){return RKK::main();}

巴特西

CF932G Palindrome Partition(回文自动机)

CF932G Palindrome Partition(回文自动机)

题解时间

最新文章

热门文章