Palindromic Magic[CF1081H]

题意

给两个字符串 $A,B$，求本质不同的字符串个数，满足该字符串由 $A$ 的一个非空回文子串和 $B$ 的一个非空回文子串拼接而成。

$|A|,|B|\leq 2\times 10^5$

记号与定义

为了方便，以下为一些记号及定义：

1，记两个字符串 $a,b$ 按顺序拼接而成的字符串为 $ab$.

2，记 $s^R$为 $s$ 按位翻转后的结果。

3，记 $\mbox border(a)$ 为一个最长的字符串，满足该字符串既是 $a$ 的前缀，也是 $a$ 的后缀。

4，记周期 $u$ 为对于任意的 $i$ 满足 $s_i=s_{i+u}$，则 $u$ 为字符串的一个周期。

5，定义循环串为：设最小的 $u$，满足 $u$ 为 $s$ 的周期，且 $u||S|$，$u\not = |S|$，则 $s$ 为循环串。

6，定义双回文串：$s=ab$，其中 $a,b$ 为非空回文串，则 $s$ 为双回文串。

7，定义非严格双回文串：严格双回文或者非空回文串。

简单性质

这些性质都比较显然。

1，若 $s$ 为回文串，则 $\mbox {border(s)}$ 为回文串。

2，若 $t=\mbox {border(s)}$，且 $2|t|\geq |s|$，则 $s$ 为回文当且仅当 $t$ 为回文。

3，若 $a,b$ 均为 $s$ 周期，且 $a+b\leq |s|$，则 $\gcd(a,b)$ 是 $s$ 的周期。

引理

引理1

描述

$s=x_1x_2=y_1y_2=z_1z_2$，且 $|x_1|<|y_1|<|z_1|$，若 $x_2,y_1,y_2,z_1$ 均为非空回文串，则 $x_1,z_2$ 也是回文串。

证明：

引理2

描述：

若 $s$ 为双回文串，设 $a$ 为最长回文前缀，$b$ 为最长回文后缀，$s=ax=yb$，则 $x,y$ 至少有一个为回文串。

证明：

由引理1推得。

引理3

若 $s$ 有两种及以上不同的弱双回文拆分，则 $s$ 为循环串。

引理4

设 $s=x_1y_1=x_2y_2=\cdots=x_my_m$ ， $\forall i\in[1,m)$， 若 $|x_i|<|x_{i+1}|$，则 $x_i=\mbox{border}(x_{i+1})$ 和 $y_{i+1}=\mbox {border}(y_i)$ 至少一个成立。

不会证。。。

题解

分析

好了写了这么多终于到重要部分了。。。

如果不是求本质不同，就是问有多少种是直接拼起来的话，那么答案就是 $a$ 和 $b$ 的本质不同的回文串的个数的乘积。

那么多出来的情况就是满足有多种双回文拆分的字符串。

由引理3可得：这个字符串是循环串。

由引理4可得：若这个字符串的一种拆分为 $s=xy$，且 $x$ 变为 $\mbox{border}(x)$ 或者 $y$ 变为 $\mbox{border}(y)$ 后仍能形成 $s$，就要减去这种情况。

所以答案就是( $a$ 和 $b$ 的本质不同的回文串的个数的乘积）- ($x$ 变为 $\mbox{border}(x)$后仍能形成 $s$ 的方案数) - ($y$ 变为 $\mbox{border}(y)$后仍能形成 $s$ 的方案数) + ($x$ 变为 $\mbox{border}(x)$ 且 $y$ 变为 $\mbox{border}(y)$ 后仍能形成 $s$ 的方案数)。

分三类讨论：

Part1

此时要算： $a$ 和 $b$ 的本质不同的回文串的个数的乘积

这个是个人都会算，对 $a,b$ 串建出 $\mbox PAM$ 后，节点个数-2 就是本质不同的回文串个数了。

Part2

此时要算：($x$ 变为 $\mbox{border}(x)$后仍能形成 $s$ 的方案数) + ($y$ 变为 $\mbox{border}(y)$后仍能形成 $s$ 的方案数)

$y$ 的情况和 $x$ 类似，我们只需考虑 $x$。

设 $x=\mbox{border}(x)w$，转换成求满足 $wS$，满足 $S,wS$ 为非空的回文串，且 $wS$ 在 $b$ 串中出现过的方案数。

由于 $w$ 为 $x$ 的最小正周期，所以 $w$ 不为循环串。

因此分类讨论一下可得：

分类1

当 $|w|\leq |S|$ 时：

此时 $|w|\leq \frac{|wS|}{2}$，又因为 $wS$ 一定是循环串，因此 $w$ 为 $wS$ 的一个周期。

若 $S\not =\mbox{border}(wS)$，则 $wS$ 存在一个小于 $w$ 的周期，因此 $w$ 为循环串，不可能。

因此只需满足 $S=\mbox{border}(wS)$即可。

用哈希算个数即可。

分类2

当 $|w|>|S|$ 时：

因为 $w$ 不为循环串，由引理3得 $w$ 最多存在一种双回文拆分，又由于 $wS,S$ 为回文串，则$w=ST$，由引理2可得知，只需要找到 $w$ 的最长回文前后缀，就可以找到 $S$，这个显然可以正反串都建立 $PAM$ 后在 $fail$ 树上倍增即可。然后还是用哈希找到是否存在 $wS$ 就可以了。注意 $S$ 不能为空串的情况。

Part3

此时要算：$x$ 变为 $\mbox{border}(x)$ 且 $y$ 变为 $\mbox{border}(y)$ 后仍能形成 $s$ 的方案数。

设 $x=w_x\mbox{border}(x),y=\mbox{border}(y)w_y$，直接用哈希算出 $w_x=w_y$ 的情况就可以啦。

Conclusion

因此需要 $PAM$ + 哈希 + 倍增。

时间复杂度 $O(n\log n)$

代码也就250行而已。

程序

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <complex>
#include <utility>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define ll long long
#define ull unsigned ll
#define db double
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define com complex<db>
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&(-(x)))
#define bit(x,i) (((x)>>(i))&1)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)

ll ans;

const int N=2e5+10;
const int S=26;
const int M=18;

const ll m1=998244353;
const ll m2=998244853;
const ll base=131;

inline ll Add1(ll x,ll y){x+=y%m1; x%=m1; return (x+m1)%m1;}
inline ll Dec1(ll x,ll y){x-=y%m1; return (x%m1+m1)%m1;}
inline ll Mul1(ll x,ll y){return ((x*y%m1)+m1)%m1;}
inline ll Add2(ll x,ll y){x+=y%m2; x%=m2; return (x+m2)%m2;}
inline ll Dec2(ll x,ll y){x-=y%m2; return (x%m2+m2)%m2;}
inline ll Mul2(ll x,ll y){return ((x*y%m2)+m2)%m2;}

struct Hint{
	ll a1,a2;
	friend inline Hint operator +(const Hint &A,const Hint &B) {return (Hint){Add1(A.a1,B.a1),Add2(A.a2,B.a2)};}
	friend inline Hint operator +(const Hint &A,const ll &B)   {return (Hint){Add1(A.a1,B),Add2(A.a2,B)};}
	friend inline Hint operator -(const Hint &A,const Hint &B) {return (Hint){Dec1(A.a1,B.a1),Dec2(A.a2,B.a2)};}
	friend inline Hint operator -(const Hint &A,const ll &B)   {return (Hint){Dec1(A.a1,B),Dec2(A.a2,B)};}
	friend inline Hint operator *(const Hint &A,const Hint &B) {return (Hint){Mul1(A.a1,B.a1),Mul2(A.a2,B.a2)};}
	friend inline Hint operator *(const Hint &A,const ll &B)   {return (Hint){Mul1(A.a1,B),Mul2(A.a2,B)};}
	friend inline bool operator <(const Hint &A,const Hint &B) {if(A.a1!=B.a1) return A.a1<B.a1; return A.a2<B.a2;}
};

namespace HASH{//双哈希
	Hint pw[N];
	inline void init(int n)
	{
		pw[0]=(Hint){1,1};
		fo(i,1,n) pw[i]=pw[i-1]*base;
	}
	inline Hint Hash(Hint *h,int l,int r){return h[r]-(h[l-1]*pw[r-l+1]);}
}
using HASH::pw;
using HASH::Hash;

struct PAM{
	int ne[N][S],fail[N],len[N],cnt,las,pos[N],ri[N];
	int s[N],n;
	int f[N][M+1];

	void init()
	{
		fail[0]=fail[1]=1; len[cnt=1]=-1; las=1;
		s[n=0]=-1;
	}
	inline int getfail(int x)
	{
		for(;s[n-1-len[x]]!=s[n];x=fail[x]);
		return x;
	}
	inline void extend(int c)
	{
		s[++n]=c;
		int p=getfail(las);
		if(!ne[p][c])
		{
			int u=++cnt,q=getfail(fail[p]);
			len[u]=len[p]+2; fail[u]=ne[q][c]; ne[p][c]=u;
		}
		las=ne[p][c];
		pos[n]=las;
		ri[pos[n]]=n;
	}
	inline void build(char *s)
	{
		int n=strlen(s+1);
		init();
		fo(i,1,n) extend(s[i]-'a');
		fo(i,0,cnt) f[i][0]=fail[i];
		fo(i,1,M)
			fo(j,0,cnt)
				f[j][i]=f[f[j][i-1]][i-1];
	}
	inline int ask(int r,int l)
	{
		int x=pos[r];
		if(len[x]<=l) return len[x];
		fd(i,M,0) if(len[f[x][i]]>l) x=f[x][i];
		return len[fail[x]];
	}
	inline bool check(int r,int len) {return ask(r,len)==len;}
};

char a[N],b[N];
PAM la,ra,lb,rb;
Hint ha[N],hb[N];
int n,m;

void init()
{
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1); m=strlen(b+1);
	HASH::init(max(n,m)+2);
	ha[0]=hb[0]=(Hint){0,0};
	fo(i,1,n)
		ha[i]=ha[i-1]*base+(a[i]-'a'+1),hb[i]=hb[i-1]*base+(b[i]-'a'+1);
	la.build(a); lb.build(b);
	reverse(a+1,a+n+1); reverse(b+1,b+m+1);
	ra.build(a); rb.build(b);
}

namespace Work1{
	//x->border(x) or y->border(y)
	//dec
	map<Hint,int> ma,mb,wa,wb;
	void init()
	{
		int t;
		fo(i,2,la.cnt)//A
		{
			ma[Hash(ha,la.ri[i]-la.len[i]+1,la.ri[i])]++;

			if((t=la.fail[i])>=2)
				if(la.len[i]<=(la.len[t]<<1))// |T|<=2|S|
					wa[Hash(ha,la.ri[i]-(la.len[i]-la.len[t])+1,la.ri[i])]++;
		}

		fo(i,2,lb.cnt)//B
		{
			mb[Hash(hb,lb.ri[i]-lb.len[i]+1,lb.ri[i])]++;
			if((t=lb.fail[i])>=2)
				if(lb.len[i]<=(lb.len[t]<<1))// |T|<=2|S|
					wb[Hash(hb,lb.ri[i]-lb.len[i]+1,lb.ri[i]-lb.len[t])]++;//!!!!!
		}
	}
	void work()
	{
		init();
		int l,r,t,bor,len;
		fo(i,2,la.cnt)
		if((t=la.fail[i])>=2)
		{
			l=la.ri[i]-(la.len[i]-la.len[t])+1;
			r=la.ri[i];
			len=r-l+1;
			ans-=wb[Hash(ha,l,r)];

			bor=la.ask(r,len);
			if(len==bor) continue;
			if(ra.check(n-l+1,len-bor))
			{
				if(mb.count(Hash(ha,l,r)*pw[len-bor]+Hash(ha,l,r-bor))) ans--;//w+S
				continue;
			}
			bor=ra.ask(n-l+1,len);
			if(la.check(r,len-bor))
			{
				if(mb.count(Hash(ha,l,r)*pw[bor]+Hash(ha,l,l+bor-1))) ans--;//w+S
				continue;
			}
		}


		fo(i,2,lb.cnt)
		if((t=lb.fail[i])>=2)
		{
			l=lb.ri[i]-lb.len[i]+1;
			r=lb.ri[i]-lb.len[t];
			len=r-l+1;
			ans-=wa[Hash(hb,l,r)];

			bor=lb.ask(r,len);
			if(len==bor) continue;
			if(rb.check(m-l+1,len-bor))
			{
				if(ma.count(Hash(hb,r-bor+1,r)*pw[len]+Hash(hb,l,r))) ans--;//S+w
				continue;
			}
			bor=rb.ask(m-l+1,len);
			if(lb.check(r,len-bor))
			{
				if(ma.count(Hash(hb,l+bor,r)*pw[len]+Hash(hb,l,r))) ans--;//S+w
				continue;
			}
		}
	}
}

namespace Work2{
	// x->border(x) and y->border(y)
	// add
	int t;
	map<Hint,int> fa,fb;
	void work()//S=XaYb
	{
		fo(i,2,la.cnt)
			if((t=la.fail[i])>=2)
				fa[Hash(ha,la.ri[i]-(la.len[i]-la.len[t])+1,la.ri[i])]++;
		
		fo(i,2,lb.cnt)
			if((t=lb.fail[i])>=2)
				fb[Hash(hb,lb.ri[i]-lb.len[i]+1,lb.ri[i]-lb.len[t])]++;
		for(auto v:fa) ans+=(ll)v.se*fb[v.fi];
	}
}

void work()
{
	ans=1ll*(la.cnt-1)*(lb.cnt-1);
	Work1::work();
	Work2::work();
	printf("%lld\n",ans);
}

int main()
{
	init();
	work();
	return 0;
}