Description
Problem 3160 万径人踪灭
这题的题面…好长,又是图片,这里就不放了
太长不看版:
给出一个全部由’a’和’b’组成的字符串,求不连续 回文 子序列(?这个应该也许不能叫子串)的方案数
如给出’aba’,’a a’就是一个符合条件的方案,而’aba’不是
Solution
当做是FFT入门题吧
为了做这道题还学了一些新姿势
好不容易弄清思路,又自己推了推细节上的问题,写出来然而WA了好几遍,后来找了个标程(不要打我)和自己对拍,发现小数据没什么问题,大数据挂了
猜测是取模的问题啊Orz
果然取模有问题,改了改交上去又跪,发现某个地方没开long long,啊,AC了,感动
把a看做1,b看做0,做一次fft求卷积,可以得到关于每个位置对称的a的个数(对称轴可以是一个数也可以是两个数的中间)
如图是’abaabaa’
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiQ3chVEa0V3bT9CX5RXa2Fmcn9CXwczLcVmds92czlGZvwVP9EUTDZ0aRJkSwk0LcxGbpZ2LcBDM08CXlpXazRnbvZ2LcRlMMVDT2EWNvwFdu9mZvwVNFp3Y5ZUblZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39DO0ETOygjM5EjNwMDM3EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
像最右边的这个2是由1*1+1*1得到的,相当于它两侧的位置上的数都会被重复的加一遍,所以之后还需要把这个问题处理掉
然后把b看做1,a看做0,再做一遍
关于某个位置对称的可非连续回文半径 x 对答案的贡献是2x−1(要问为什么的话,感觉这里写的比较清楚QvQ http://blog.csdn.net/wzq_qwq/article/details/48173545)
但是这个答案是可连续可不连续的方案数,于是再用Manacher算出(连续的)回文子串数,减掉就好了
(Manachar我其实是现学的…https://segmentfault.com/a/1190000003914228)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define Min(a,b) (a<b?a:b)
#define Max(a,b) (a>b?a:b)
#define pi acos(-1.0)
#define MAXN 400005
#define Mod 1000000007
using namespace std;
struct cp
{
double r,i;
cp(double r=,double i=):r(r),i(i){}
cp operator + (const cp& x)
{return cp(r+x.r,i+x.i);}
cp operator - (const cp& x)
{return cp(r-x.r,i-x.i);}
cp operator * (const cp& x)
{return cp(r*x.r-i*x.i,r*x.i+i*x.r);}
};
char s[MAXN];
long long Pow(long long x,long long n)
{
long long ans=;
while(n>)
{
if(n&)
{
ans*=x;
ans%=Mod;
}
x=(x*x)%Mod;
n>>=;
}
return ans;
}
void brc(cp *x,int l)
{
for(int i=,j=l/;i<l-;i++)
{
if(i<j)swap(x[i],x[j]);
int k=l/;
while(j>=k)
{
j-=k;
k/=;
}
if(j<k)j+=k;
}
}
void fft(cp *x,int l,int on)
{
brc(x,l);
for(int h=;h<=l;h<<=)
{
cp wn(cos(on**pi/h),sin(on**pi/h));
for(int j=;j<l;j+=h)
{
cp w(,);
for(int k=j;k<j+h/;k++)
{
cp u=x[k];
cp t=w*x[k+h/];
x[k]=u+t;
x[k+h/]=u-t;
w=w*wn;
}
}
}
if(on==-)for(int i=;i<l;i++)x[i].r/=l;
}
int rl[MAXN];
long long manachar(char *s,int l)
{
memset(rl,,sizeof(rl));
char s1[MAXN*];
int Maxright=-,pos=;
long long res=;
for(int i=;i<l;i++)
{
s1[i*]='#';
s1[i*+]=s[i];
}
s1[l*]='#';
l=l*+;
for(int i=;i<l;i++)
{
if(i<Maxright){
rl[i]=Min(rl[*pos-i],Maxright-i);
}
else rl[i]=;
while(i-rl[i]>=&&i+rl[i]<l&&s1[i-rl[i]]==s1[i+rl[i]])
rl[i]++;
if(i+rl[i]->Maxright)
{
Maxright=i+rl[i]-;
pos=i;
}
res+=(rl[i]/)%Mod;
res%=Mod;
}
return res;
}
cp x1[MAXN],x2[MAXN];
int main()
{
scanf("%s",s);
int l=strlen(s),L=;
long long ans=;
while(L<l*)L<<=;
for(int i=;i<l;i++)
{
if(s[i]=='a')x1[i]=cp(,);
else x1[i]=cp(,);
}
for(int i=l;i<L;i++)
x1[i]=cp(,);
fft(x1,L,);
for(int i=;i<L;i++)x1[i]=x1[i]*x1[i];
fft(x1,L,-);
for(int i=;i<l;i++)
{
if(s[i]=='b')x2[i]=cp(,);
else x2[i]=cp(,);
}
for(int i=l;i<L;i++)
x2[i]=cp(,);
fft(x2,L,);
for(int i=;i<L;i++)x2[i]=x2[i]*x2[i];
fft(x2,L,-);
for(int i=;i<L;i++)
{
int t=(int)(x1[i].r+x2[i].r+);
t=(t+)/;
ans+=(Pow(,t)-)%Mod;
ans%=Mod;
}
ans-=manachar(s,l);
ans+=Mod;
ans%=Mod;
printf("%d\n",ans);
return ;
}