3160: 万径人踪灭

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 1440  Solved: 799

Description

Input

Output

Sample Input

Sample Output

HINT

Source

【分析】

  看题目被吓死,其实很多废话。。

  还是自己想出来了。。FFT好强啊。。可以加速很多东西的说。

  然后就是,枚举对称轴吧?

  假设a[i]==a[j],那么用i+j表示它的对称轴。

  共有0~2*n的对称轴,对于每个对称轴它的对称点对个数就是$F[k]=\sum s[k-i]==s[k+i]$

  注意到只有a和b,假设只考虑a相同,令$a[i]=s[i]=='a'?1:0$

  那么就是$F[k]=\sum a[k-i]*a[k+i]$

  化成卷积形式,可以用FFT做了。用b也做一遍

  最后答案是$\sum 2^{F[k]}$-空串-回文子串(不能连续嘛)

  回文子串我用马拉车打了,,,然后打错了,,,然后TLE了,,,以为是FFT的递归版太慢,还去学了迭代打法【醉生梦死。。。

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 100010*8
#define Mod 1000000007
#define LL long long
const double pi=acos(-); int mymin(int x,int y) {return x<y?x:y;} struct P
{
double x,y;
P() {x=y=;}
P(double x,double y):x(x),y(y){}
friend P operator + (P x,P y) {return P(x.x+y.x,x.y+y.y);}
friend P operator - (P x,P y) {return P(x.x-y.x,x.y-y.y);}
friend P operator * (P x,P y) {return P(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);}
}a[Maxn];
int i,j,k; int nn=,R[Maxn];
void fft(P *a,int f)
{
for(i=;i<nn;i++) if(i<R[i]) swap(a[i],a[R[i]]);
for(i=;i<nn;i<<=)
{
P wn(cos(pi/i),f*sin(pi/i));
for(int ad=i<<,j=;j<nn;j+=ad)
{
P w(,);
for(k=;k<i;k++,w=w*wn)
{
P x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y;a[j+k+i]=x-y;
}
}
}
} char s[Maxn];
int ans[Maxn]; int aa[Maxn],pp[Maxn];
int get_manacher(int ll)
{
int mx=,id=;
for(int i=;i<=ll;i++)
{
int k;
if(i<mx) k=mymin(pp[*id-i],mx-i+);
else k=;
while(aa[i+k]==aa[i-k]&&i-k>=&&i+k<=ll) k++;
pp[i]=k;
if(i+pp[i]->mx) mx=i+pp[i]-,id=i;
}
int as=;
for(int i=;i<=ll;i+=) as=(as+(pp[i]+)/)%Mod;
for(int i=;i<=ll;i+=) as=(as+pp[i]/)%Mod;
return as;
} int bin[Maxn]; int main()
{
scanf("%s",s);
int n=strlen(s);n--;
for(i=;i<=n;i++) a[i].x=(s[i]=='a'?:); int ll=;nn=;
while(nn<=n+n) ll++,nn<<=;
for(i=;i<nn;i++) R[i]=(R[i>>]>>)|((i&)<<(ll-)); fft(a,);for(i=;i<=nn;i++) a[i]=a[i]*a[i];fft(a,-);
for(i=;i<=n+n;i++) ans[i]=(int)(a[i].x/nn+0.5); for(i=;i<=nn;i++) a[i].x=a[i].y=;
for(i=;i<=n;i++) a[i].x=(s[i]=='a'?:),a[i].y=; fft(a,);for(i=;i<=nn;i++) a[i]=a[i]*a[i];fft(a,-);
for(i=;i<=n+n;i++) ans[i]+=(int)(a[i].x/nn+0.5); for(i=;i<=n+n;i++) ans[i]=(ans[i]+)/;
int a1=;
bin[]=;for(i=;i<=n;i++) bin[i]=(bin[i-]*)%Mod;
for(i=;i<=n+n;i++) a1=(a1+bin[ans[i]])%Mod;
a1-=n+n+;
aa[]=;for(int i=;i<=n;i++) aa[*i+]=s[i]-'a',aa[*i+]=;aa[*n+]=;
a1-=get_manacher(*n+);
a1=(a1%Mod+Mod)%Mod;
printf("%d\n",a1);
return ;
}

【所以我现在会迭代打法了hhh

2017-04-13 18:42:35

最新文章

  1. G++ 参数介绍(转载)
  2. 线程生命周期状态UML图
  3. hadoop——配置eclipse下的map-reduce运行环境 1
  4. java中途强制跳出递归
  5. Java Web整合开发(4) -- JSP
  6. 初探JavaScript魅力(五)
  7. X-Scan使用教程
  8. 利刃 MVVMLight
  9. 玩转Storage Table 的PartitionKey,RowKey设计
  10. 《XXX重大技术需求征集系统》的可用性和可修改性战术分析
  11. django 分类搜索(根据不同的单选框,改变form提交的地址)
  12. GeoGlobe Server使用问题收集
  13. [主席树 强制在线]ZOJ3888 Twelves Monkeys
  14. 解决jsfl 弹出警告
  15. SD从零开始19-20
  16. Mysql5.7初始化成空密码或随机密码的方式
  17. Centos7安装killall,fuser, killall,pstree和pstree.x11
  18. C++11中右值引用和移动语义
  19. 第一周冲刺评论总结&amp;&amp;针对评论总结的改进
  20. Mac下,如何把项目托管到Github上(Github Desktop的使用)

热门文章

  1. (function($){})(jQuery)---Javascript的神级特性:闭包
  2. oracle查看表中数据的大小
  3. itext 生成pdf文件添加页眉页脚
  4. vscode中go插件配置
  5. React 16 源码瞎几把解读 【二】 react组件的解析过程
  6. Producer Flow Control 和 vmQueueCursor
  7. django 项目中的 favicon.ico 处理
  8. java版云笔记(二)
  9. alias命令别名
  10. [置顶] 人工智能(深度学习)加速芯片论文阅读笔记 (已添加ISSCC17,FPGA17...ISCA17...)