BZOJ 3160: 万径人踪灭

admin — Fri, 20 Jan 2017 22:21:00 +0800

###Description
略。见[BZOJ3160][1]

###Solution
对于“不能是连续的一段”，可以先计算所有答案，然后减去连续一段的，即回文串，这个用回文自动机或者manacher可以得出
考虑以每个位置为中心的对称元素对个数f[i]，那么i位置对答案的贡献是$$2^{f[i]}-1$$
如果把a视为1，b视为-1，然后把原串长度\*4，卷积，那么以i为中心的元素对如果相同，则贡献1，否则贡献-1

###Code
```c++
#include<bits/stdc++.h>
typedef double lf;

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)

inline int mod(int x,int y){if(x>=y)return x-y;return x;}

#define N 524288

struct num
{
	lf r,i;
	num(){r=i=0;}
	num(lf x){r=x,i=0;}
	num(lf x,lf y){r=x,i=y;}
	num(const num &x){r=x.r,i=x.i;}
	inline num& operator +=(const num &x){r+=x.r,i+=x.i;}
	inline num& operator -=(const num &x){r-=x.r,i-=x.i;}
	inline num& operator *=(const num &x){lf a=r*x.r-i*x.i,b=r*x.i+i*x.r;r=a,i=b;}
	inline num operator +(const num &x){num t=*this;t+=x;return t;}
	inline num operator -(const num &x){num t=*this;t-=x;return t;}
	inline num operator *(const num &x){num t=*this;t*=x;return t;}
};

int id[N];
num tx[N],mf[N];

inline void init_id(int y)
{
	fo0(i,1<<y)id[i]=id[i>>1]>>1|(i&1)<<y-1;
}

#define idft(a,b) dft(a,b,1)

inline void dft(num *s,int n,bool II=0)
{
	fo0(i,1<<n)tx[i]=s[id[i]];
	fo1(p,n)
	{
		lf tmp=M_PI*2/(1<<p);
		if(II)tmp=-tmp;
		num t0(1),t1(cos(tmp),sin(tmp));
		fo0(i,1<<p-1)mf[i]=t0,t0*=t1;
		num X,Y;
		for(int i=0,ie=1<<p,ir=ie/2,pp=ir-1;i<(1<<n);i+=ie)fo0(j,ir)
		{
			X=tx[i|j],Y=tx[i|j|ir]*mf[j];
			tx[i|j]=X+Y,tx[i|j|ir]=X-Y;
		}
	}
	fo0(i,1<<n)s[i]=tx[i];
}

#define N2 100010

struct node
{
	int len,cnt;
	node *nxt[2],*fail;
}t[N2+2],*tm=t+2;

inline void build(char *s,int n)
{
	t[0].len=0,t[1].len=-1;
	node *cur=t+1,*tmp,*t2;
	t[0].fail=t+1;
	for(int i=0;i<n;i++)
	{
		char u=s[i]-'a';
		for(;s[i]!=s[i-1-cur->len];cur=cur->fail);
		if(cur->nxt[u])
			cur=cur->nxt[u],cur->cnt++;
		else
		{
			tmp=cur->nxt[u]=tm++;
			tmp->len=cur->len+2;
			tmp->cnt=1;
			if(tmp->len==1)
				tmp->fail=t;
			else
			{
				for(t2=cur->fail;s[i]!=s[i-1-t2->len];t2=t2->fail);
				tmp->fail=t2->nxt[u];
			}
			cur=tmp;
		}
	}
}

inline void count()
{
	for(node *x=tm-1;x>=t;x--)
		if(x->fail)x->fail->cnt+=x->cnt;
}

#define P 1000000007

inline int cnt()
{
	int ans=0;
	for(node *x=tm-1;x>t+1;x--)
		ans=mod(ans+x->cnt,P);
	return ans;
}

char s[100000];
num p[N];
int po[100001];

int main()
{
	scanf("%s",s);
	int n=strlen(s);
	fo1(i,n/2+5)po[i]=mod(mod(po[i-1]*2+1,P),P);
	int y=0;
	while((1<<(y+1))<n*4)y++;y++;
	fo0(i,n)p[i]=s[i]=='a'?1:-1;
	init_id(y);
	dft(p,y);
	fo0(i,1<<y)p[i]*=p[i];
	idft(p,y);
	lf t=1.0/(1<<y);
	int ans=0;
	fo0(i,n*2-1)
	{
		int cnt=round(p[i].r*t);
		cnt=(std::min(i/2+1,(n*2-i)/2)+(cnt&1?(cnt+1)/2:cnt/2))/2;
		ans=mod(ans+po[cnt],P);
	}
	build(s,n);
	count();
	printf("%d",mod(ans+P-cnt(),P));
}
```

[1]: http://www.lydsy.com/JudgeOnline/problem.php?id=3160

mcfx's blog - 回文自动机

BZOJ 3160: 万径人踪灭