NKOJ 2895 万径人踪灭（Manacher+FFT）

发表于 |
字数统计: 1,800字 | 阅读时长 ≈ 8min

P2895 万径人踪灭

题目描述

如果机房马上要关门了，或者你急着要和MM 约会，请直接跳到第六个自然段。
VFleaKing注意到了这条上山下山的土路，有些地方能欣赏到美景，有些地方则不能。把上山的道路每10cm分为一小段，则对于每一小段，用a 表示能欣赏到美景，用b表示不能欣赏到美景，就能得到一个只含a,b的字符串s。当然由于下山和上山是一条路，所以下山的道路的字符串就是将上山的道路的字符串反过来。设上山字符串长度为n，每个字符依次为s1,s2,…,sn。在上山和下山的路上，VFleaKing会选择某些小段查看旁边的景色，其他时间低头走路。即VFleaKing会选择k个小段x1,x2,…,xk且k>=1,1<=x1 < x2< …< xk<=n，VFleaKing上山和下山的过程中会在这些地方查看景色。
这里写图片描述
VFleaKing 希望，上山下山时看到的美景的情况相同。也就是说，VFleaKing 上山时是否看到了美景的情况是：sx1,sx2,…,sxk，记为字符序列T1，下山时是否看到了美景的情况是：sxk,sxk-1,…,sx1，记为字符序列T2。VFleaKing希望T1=T2。
VFleaKing还希望，上山下山时查看景色的间隔相等。也就是说，上山时查看景色的间隔为：x2-x1,x3-x2,…,xk-xk-1，记为数列P1。下山时查看景色的间隔为：xk-xk-1,xk-1-xk-2,…,x2-xk-1，记为数列P2。VFleaKing希望P1=P2。
VFleaKing觉得，如果第一次查看景色和最后一次查看景色这段时间里，没有一次低头看路他就会摔倒。也就是说，如果对于所有1<=i<=k 都有xi=x1+i-1，VFleaKing就会摔倒，VFleaKing 不希望发生这样的情况。
就是要在一个只含a,b的字符串中选取一个子序列，使得：

  1. 位置和字符都关于某条对称轴对称。
  2. 不能是连续的一段。
    以s=“abaaaaabbabbabaa”为例。如果我们用符号[a1,a2,…,ak]表示一个序列，那么[1,4]
    就是一个合法的序列x，[5,8,10,12,15]也是，[4,5,8,9,10,11,12,15,16]也是。但是[1,2]不满足VFleaKing第一个希望和第三个希望，所以不是。[1,2,4]不满足第二个希望，所以不是。[9,10,11]不满足第三个希望，所以不是。
    这里写图片描述
    给你字符串s，现在VFleaKing 想知道，有多少个合法的x。答案可能很大，VFleaKing想知道结果对1000000007取模的值。

输入格式

一行，一个只包含a,b两种字符的字符串。

输出格式

一行，一个非负整数表示问题的答案。

样例输入1：

abaabaa

样例输入2：

aaabbbaaa

样例输入3：

aaaaaaaa

样例输出1：

14

样例输出2：

44

样例输出3：

53

样例解释：

第一组：14 个方案分别是：[1,3],[1,4],[2,5],[1,6],[3,6],[4,6],[1,7],[3,7],[4,7],[1,4,7],[3,5,7],[1,3,4,6],[1,2,5,6],[3,4,6,7].
第二组：不解释
第三组：不解释

数据范围：

对于10%的数据，字符串仅包含字母a或仅包含字母b。
另有20%的数据，n<=1000。
另有20%的数据，要么a的个数不超过10，要么b的个数不超过10。
另有10%的数据，n<=10000。
对于100%的数据，n<=100000。

这道题真是劲啊！
显然的可以想到如果选出的串是连续的，那么答案是容易统计的，但是问题是处理不连续的。
首先在相邻两个字符之间添加一个字符，这样奇数和偶数的问题就解决了。

然后考虑以某个位置为对称中心，能够选出多少种方案，为了统计这个方案，显然我们需要知道有多少对字符串以该点为对称中心。
那么先假设总共有$X$对字符以该点为中心对称（它本身也算）。
再考虑到题目提出的必须要休息一次的要求，即必须是至少不相连的两段，容易想到统计出以该点为中心，向两边的连续的相同字符有$Y$对。
那么以该点为对称中心的方案数$S=2^X-Y-1$，意思是每一对字符都可以选择取或不取，然后减掉只有一段的情况和空串的情况。

那么现在如何统计出$X$和$Y$呢。$Y$显然用$Manacher$直接得到。考虑$X$。

观察之后容易发现，只存在了两种字符，那么将$a$出现的位置记录到一个序列$A[i]$中，$A[i]=1当且仅当s[i]=a$,同理将$B[i]$也统计出来，至于新加的字符并不影响答案，不考虑。

那么很容易发现对于一个位置$K$，$X_K=\sum{(A[i]\times A[2K-i]+B[i]\times B[2K-i])}$，那么显然用$FFT$处理即可。

最后枚举每个点求和即可。$Ans=\sum{(2^{X_i}-Y_i-1)}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<complex>
#include<cmath>
#define N 1000005
#define ll long long
using namespace std;
char s[N],ss[N];
ll L,Max,rad[N],pos,T[N],P[N];
const ll mod=1000000007;
const double pi=4.0*atan(1.0);
complex<double>A[N],B[N],wi[N];
void Manacher()
{
	ll i,j,k;
	for(i=1;i<=L;i++)
	{
		if(i>Max)rad[i]=1;
		else rad[i]=min(Max-i+1,rad[2*pos-i]);
		while(i-rad[i]&&i+rad[i]<=L&&s[i-rad[i]]==s[i+rad[i]])rad[i]++;
		if(i+rad[i]-1>Max)Max=i+rad[i]-1,pos=i;		
	}
}
void FFT(complex<double>W[],ll n,ll ty)
{
	ll i,j,k,m;
	complex<double>t0,t1;
	for(i=0;i<n;i++)
	{
		for(j=0,k=i,m=1;m<n;m<<=1,j=(j<<1)|(k&1),k>>=1);
		if(i<j)swap(W[i],W[j]);
	}
	wi[0]=1;
	for(m=1;m<n;m<<=1)
	{
		t0=exp(complex<double>(0,ty*pi/m));
		for(i=1;i<m;i++)wi[i]=wi[i-1]*t0;
		for(k=0;k<n;k+=m<<1)
		for(i=k;i<m+k;i++)
		{
			t0=W[i];
			t1=W[i+m]*wi[i-k];
			W[i]=t0+t1;
			W[i+m]=t0-t1;
		}
	}
	if(ty==1)return;t0=1.0/n;
	for(i=0;i<n;i++)W[i]*=t0;
}
int main()
{
	ll i,j,k,n=1,ans=0;
	scanf("%s",&ss[1]);ss[0]=s[0]='%';
	L=strlen(ss)-1;
	for(i=1;i<=L;i++)
	{
		s[i<<1]=ss[i];
		s[i<<1|1]='$';
		s[i*2-1]='$';
	}
	L=strlen(s)-1;Manacher();
	while(n<2*L)n<<=1;
	for(i=1;i<=L;i++)
	{
		if(s[i]=='a')A[i]+=1;
		if(s[i]=='b')B[i]+=1;
	}
	FFT(A,n,1);FFT(B,n,1);
	for(i=0;i<=n;i++)A[i]*=A[i],B[i]*=B[i];
	FFT(A,n,-1);FFT(B,n,-1);
	for(i=1;i<=L;i++)
	{
		T[i]=floor(A[i<<1].real()+0.5)+floor(B[i<<1].real()+0.5);
		T[i]=T[i]+1>>1;
	}
	P[0]=1;for(i=1;i<=L;i++)P[i]=P[i-1]<<1,P[i]%=mod;
	for(i=1;i<=L;i++)ans=(ans+P[T[i]]-rad[i]/2-1)%mod;
	printf("%lld",(ans+mod)%mod);
}