bzoj3160 万径人踪灭
题目在上方链接 Description
Input
Output
Sample Input
Sample Output
HINT
Source
2013湖北互测week1
首先将字符串中间插入”#” 把他们分隔开
题目要求求不连续的回文串的个数 那么就用总数减去连续的即可 考虑连续的部分 直接用manacher求即可 算出长度 然后再/2就是答案
不连续的怎么办 考虑现在用#将他们隔开 然后假如只考虑字符是a的贡献
那么 显然字符a都会出现在偶数位置上 那么想办法知道一个位置左右对称的符合要求的字符即可得到答案 比如#a#b#a这样关于b左右对称的就是2 然后答案就是2^2-1
那么想办法计算出左右对称位置符合要求的这个t即可
设当前在第k位
f[k]=∑i不越界[k−imod2=0][sk−i=′a′][sk+i=′a′]
f
[
k
]
=
∑
i
不
越
界
[
k
−
i
mod
2
=
0
]
[
s
k
−
i
=
′
a
′
]
[
s
k
+
i
=
′
a
′
]
∑t∑i不越界[k−i=2×t][sk−i2=′a′][sk+i2=′a′]
∑
t
∑
i
不
越
界
[
k
−
i
=
2
×
t
]
[
s
k
−
i
2
=
′
a
′
]
[
s
k
+
i
2
=
′
a
′
]
∑t∑i不越界[k−i=2×t]st∗sk−t
∑
t
∑
i
不
越
界
[
k
−
i
=
2
×
t
]
s
t
∗
s
k
−
t
∑t[k−2∗t>=0]st∗sk−t
∑
t
[
k
−
2
∗
t
>=
0
]
s
t
∗
s
k
−
t
∑t=0⌊k2⌋st∗sk−t
∑
t
=
0
⌊
k
2
⌋
s
t
∗
s
k
−
t
然后两次dft一次idft即可
#include#include#include#include#define pi acos(-1)#define ll long longusing namespace std;const int mod=1000000007;const int N=100020;struct C{ double a,b; inline friend C operator +(const C &x,const C &y){return (C){x.a+y.a,x.b+y.b};} inline friend C operator -(const C &x,const C &y){return (C){x.a-y.a,x.b-y.b};} inline friend C operator *(const C &x,const C &y){return (C){x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a};} inline void operator *=(const C &y){*this=*this*y;}}a[N<<2],b[N<<2];int n,m,R[N<<2],p[N<<1];ll ans;inline void fft(C *x,int f){ for (int i=0;i>=1) if (t&1) tmp=tmp*b%mod;return tmp;}char s[N],s1[N<<1];templateinline void add(T &x,int v){x=x+v>=mod?x+v-mod:x+v;}templateinline void dec(T &x,int v){x=x-v<0?x-v+mod:x-v;}int main(){ freopen("bzoj3160.in","r",stdin); scanf("%s",s+1);m=strlen(s+1);m<<=1; int t=0;for (n=1;n<=m;n<<=1,++t);m>>=1; for (int i=0;i>1]>>1)|((i&1)<>1))-1);s1[++m]='#';// for (int i=1;i<=m;++i) printf("%lf\n",a[i].a);// for (int i=2;i<=m;++i) printf("%d\n",(int)(a[i].a+0.1)>>1); for (int i=1;i<=m;++i){ if (i0&&i+p[i]<=m&&s1[i-p[i]]==s1[i+p[i]]) ++p[i]; if(i+p[i]>mx) mx=i+p[i],id=i;dec(ans,p[i]>>1); }// for (int i=1;i<=m;++i) printf("%d ",p[i]); printf("%lld\n",ans); return 0;}
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
暂时没有评论,来抢沙发吧~