「bzoj3160」万径人踪灭 - 生成函数+Manacher/回文自动机

题目大意

    给定一个仅由a和b构成的字符串，求其位置关于某条对称轴对称的不完全连续回文串。

---

题目分析

正向思考比较困难，考虑补集转化。
位置关于某条对称轴对称的不完全连续回文串$=$位置关于某条对称轴对称的任意回文串$-$连续回文串。

其中，连续回文串数目是很好求的，直接上马拉车算法或回文自动机。
因此，只需考虑如何求出 位置关于某条对称轴对称的任意回文串 数目。

如图，我们枚举每一个对称轴，求出其最长可非连续回文长度，也就是有多少个字母能够对称。
上图的最长可非连续回文长度为$3$，故一共能形成$2^3-1=7$个位置关于对称轴对称的任意回文串（考虑每个字母选与不选，除去空串）。
因此，我们现在需要求出以每个对称轴对称的最长可非连续回文长度$f[i]$。
朴素的求法是$O(n^2)$的。

我们将串进行扩展，使其能够表示出间隙。
如例中$s=$ababaaab扩展为$s’=$a#b#a#b#a#a#a#b。
考虑，若$s_0=a$与$s_5=a$关于$s_{2.5}$的间隙对称，也就是$s’_5$。
因此：

$$f[i]=\left\lfloor\frac{1+\sum\limits_{j=0}^i[s_j=s_{i-j}]}2\right\rfloor$$

其中除以$2$是因为对称每个字母会被算两次，$+1$是因为如果对称轴在字母上只会计算一次。

令：

$$g[i]=\sum\limits_{j=0}^i[s_j=s_{i-j}]$$

则：

$$f[i]=\left\lfloor\frac{1+g[i]}2\right\rfloor$$

$g[i]$很明显是一个卷积，我们可以先将$s$转化为多项式：

• 将$a$变为$1$，$b$变为$0$，如样例$s=ababaaab$，转化为多项式： $$1x^0+0x^1+1x^2+0x^3+1x^4+1x^5+1x^6+0x^7$$ 对多项式进行平方，对应项系数记为$g_1[i]$。
• 将$b$变为$1$，$a$变为$0$，如样例$s=ababaaab$，转化为多项式： $$0x^0+1x^1+0x^2+1x^3+0x^4+0x^5+0x^6+1x^7$$ 对多项式进行平方，对应项系数记为$g_2[i]$。

因此$g[i]=g_1[i]+g_2[i]$。
问题解决。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<complex>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

#define cp complex<double>
typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=262144+5;
const LL mod=1e9+7;
const double pi=acos(-1);

struct FastFourierTransform {
	int n;
	cp omega[maxn],iomega[maxn];
	
	void init(int n) {
		this->n=n;
		for(int i=0; i<n; i++) {
			omega[i]=cp(cos(2*pi/n*i),sin(2*pi/n*i));
			iomega[i]=conj(omega[i]);
		}
	}
	
	void transform(cp* a,cp* omega) {
		int k=log2(n);
		for(int i=0; i<n; i++) {
			int t=0;
			for(int j=0; j<k; j++)if(i&(1<<j))t|=(1<<(k-j-1));
			if(i<t)swap(a[i],a[t]);
		}
		for(int len=2; len<=n; len*=2) {
			int mid=len>>1;
			for(cp* p=a; p!=a+n; p+=len)
				for(int i=0; i<mid; i++) {
					cp t=omega[n/len*i]*p[mid+i];
					p[mid+i]=p[i]-t;
					p[i]+=t;
				}
		}
	}

	void dft(cp* a) {
		transform(a,omega);
	}

	void idft(cp* a) {
		transform(a,iomega);
		for(int i=0; i<n; i++)a[i]/=n;
	}
} fft;

void Multiply(const int* a1,const int n1,const int* a2,const int n2,int* ans) {
	int n=1;
	while(n<n1+n2)n<<=1;
	static cp c1[maxn],c2[maxn];
	fill(c1,c1+n,0);
	fill(c2,c2+n,0);
	for(int i=0; i<n1; i++)c1[i].real(a1[i]);
	for(int i=0; i<n2; i++)c2[i].real(a2[i]);
	fft.init(n);
	fft.dft(c1);
	fft.dft(c2);
	for(int i=0; i<n; i++)c1[i]*=c2[i];
	fft.idft(c1);
	for(int i=0; i<n1+n2-1; i++)ans[i]+=round(c1[i].real());
}

struct Palindsome_Automaton {
	int child[maxn][28];
	int n,size,last,s[maxn],len[maxn],next[maxn];
	LL cnt[maxn];
	Palindsome_Automaton() {
		size=-1;
		newnode(0); //even
		newnode(-1); //odd
		last=n=0;
		s[0]=-1;
		next[0]=next[1]=1;
	}
	int newnode(int v) {
		int now=++size;
		memset(child[now],0,sizeof(child[now]));
		next[now]=0;
		len[now]=v;
		return now;
	}
	void insert(int data,int id) {
		s[++n]=data;
		int p=last;
		while(s[n-len[p]-1]!=s[n])p=next[p];
		if(!child[p][data]) {
			int now=newnode(len[p]+2),q=next[p];
			while(s[n-len[q]-1]!=s[n])q=next[q];
			next[now]=child[q][data];
			child[p][data]=now;
		}
		last=child[p][data];
		cnt[last]++;
	}
	void build(string s) {
		int tot=0;
		for(auto x:s)insert(x-'a',++tot);
	}
	void count() {
		for(int i=size; i>=0; i--)cnt[next[i]]+=cnt[i];
	}
} pam;

char s[maxn];
int len,a[maxn],b[maxn],f[maxn];
LL bit[maxn],ans=0;

int main() {
	scanf("%s",s);
	len=strlen(s);
	bit[0]=1;
	for(int i=1; i<=len; i++)bit[i]=(bit[i-1]<<1)%mod;
	for(int i=0; i<len; i++)a[i]=b[i]=s[i]=='a';
	Multiply(a,len,b,len,f);
	for(int i=0; i<len; i++)a[i]=b[i]=s[i]=='b';
	Multiply(a,len,b,len,f);
	for(int i=0; i<=2*len-2; i++)ans=(ans+bit[(f[i]+1)>>1]-1)%mod;
	pam.build(s);
	pam.count();
	for(int i=2; i<=pam.size; i++)ans=(ans-pam.cnt[i]%mod+mod)%mod;
	printf("%lld\n",ans);
	return 0;
}