bzoj3160 万径人踪灭

题意:在一个仅仅含有a,b的字符串里选取一个子序列,使得:

  1. 位置和字符都关于某条对称轴对称;
  2. 不能是连续的一段。

求方案数,取模。

题解:

PoPoQQQ的题解

大致上是个这样的思路:用所有回文子序列的数量减去所有的连续回文串数量就是答案。然后令$f[i]$为以$i$为对称轴的对称字符对数,由于$i$有可能是一条夹缝,所以像manacher那样将字符串用#分隔,所有回文子序列数就是$\sum _{i=1}^{2n+1} (2^{f[i]}-1)$。用这个减掉manacher求得的连续回文字串的个数就可以了。

对于求$f[i]$,若原串$s[i]$与$s[j]$对称(以0开始为下标),那么在分隔以后的串里对称轴为$mid$,$i+j=mid-2$,所以$f[i]=\lfloor \frac{\sum_{j=0}^{i-2}[s[j]==s[i-2-j]+1}{2} \rfloor$,除以2是因为除了中间仅一个的情况外,每对都算了两次。$s[j]==s[i-2-j]$可以看为,如果两个字符都为a,那么原串中为a的地方设为$1$,其他为$0$,这样的话可以发现这个实质上可以看作$\sum_{j=0}^{i-2}s[j]\cdot s[i-2-j]$,是一个卷积,$fft$计算即可。对求b的对称对同理。

复杂度$O(nlogn+n)$。

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
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const int mo=(int)1e9+7;
char s[maxn],m[maxn<<1];
int n;
ll f[maxn<<1],fac[maxn];
typedef complex<double > cpl;
const double Pi=acos(-1.0);
cpl omg[1<<18],rmg[1<<18];
void fft(cpl *a,int n,cpl *o)
{
int k=0;
while((1<<k)<n) k++;
assert((1<<k)==n);
for(int i=0;i<n;i++) {
int t=0;
for(int j=0;j<k;j++) if((i>>j)&1) t|=(1<<(k-j-1));
if(t>i) swap(a[i],a[t]);
}
cpl t;
for(int l=2;l<=n;l<<=1) {
int hf=l>>1;
for(cpl *x=a;x!=a+n;x+=l)
for(int i=0;i<hf;i++) {
t=o[n/l*i]*x[hf+i];
x[hf+i]=x[i]-t; x[i]+=t;
}
}
}
void dft(cpl *a,int n) {fft(a,n,omg);}
void idft(cpl *a,int n)
{
fft(a,n,rmg);
for(int i=0;i<n;i++) a[i]/=n;
}
void Mul(cpl *a,int n1,cpl *b,int n2)
{
int n=1;
while(n<(n1+n2-1)) n<<=1;
for(int i=0;i<n;i++) omg[i]=cpl(cos(i*2*Pi/n),sin(i*2*Pi/n)),rmg[i]=conj(omg[i]);
dft(a,n), dft(b,n);
for(int i=0;i<n;i++) a[i]*=b[i];
idft(a,n);
}
int kgm[maxn<<1];
ll Manacher(char *s,int n)
{
int mx=-1,pos=-1;
for(int i=0;i<n;i++) {
if(mx>=i) kgm[i]=min(mx-i+1,kgm[pos*2-i]);
else kgm[i]=1;
while(i-kgm[i]>=0 && i+kgm[i]<n && s[i-kgm[i]]==s[i+kgm[i]]) kgm[i]++;
if(i+kgm[i]-1>mx) mx=i+kgm[i]-1,pos=i;
}
ll ret=0;
for(int i=0;i<n;i++) ret=(ret+kgm[i]/2)%mo;
return ret;
}
int main()
{
scanf("%s",s);
n=strlen(s);
fac[0]=1ll;for(int i=1;i<maxn;i++) fac[i]=fac[i-1]*2%mo;
int L=0;
m[L++]='$';
for(int i=0;i<n;i++) {
if(L&1) m[L++]='#';
m[L++]=s[i];
}
m[L++]='#';m[L]='\0';
static cpl a[1<<18],b[1<<18],a1[1<<18],b1[1<<18];
for(int i=0;i<n;i++) a[i]=cpl((s[i]=='a'),0),a1[i]=a[i],b[i]=cpl((s[i]=='b'),0),b1[i]=b[i];
Mul(a,n,a1,n); Mul(b,n,b1,n);
int N=1;
while(N<(n*2-1)) N<<=1;
for(int i=2;i<L;i++) f[i]=(f[i]+((int)round(a[i-2].real())+1)/2), f[i]=(f[i]+((int)round(b[i-2].real())+1)/2);
ll res=0;
for(int i=0;i<L;i++) res=(res+fac[f[i]]%mo-1+mo)%mo;
printf("%lld\n",(res-Manacher(m,L)+mo)%mo);
return 0;
}