Solution
$ans=$回文子序列$-$回文子串的数目。
后者可以用$manacher$直接求。
前者设$f[i]$表示以$i$为中心的对称的字母对数。
那么回文子序列的数量也就是$\sum_{i=0}^{n-1}2^{f[i]-1}$
构造两个数组$a[i],b[i]$。若第$i$位为$a$,那么$a[i]=1$,否则$b[i]=1$。
可以发现$a$数组自身卷积就是$a$字母对$f$数组的贡献,$b$数组同理。
卷下$a$,卷下$b$,对应位置求和,就是$f$数组。
因为在卷积中每对对称字符被算了两次,而自己和自己关于自己对称只算了一次,所以要把答案除2向上取整。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N (400009)
#define LL long long
#define MOD (1000000007)
using namespace std; int n,fn,l,tot,r[N],len[N],p[N];
LL Re,fun;
char s[N],st[N];
double pi=acos(-1.0);
struct complex
{
double x,y;
complex (double xx=,double yy=)
{
x=xx; y=yy;
}
}a[N],b[N]; complex operator + (complex a,complex b) {return complex(a.x+b.x,a.y+b.y);}
complex operator - (complex a,complex b) {return complex(a.x-b.x,a.y-b.y);}
complex operator * (complex a,complex b) {return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
complex operator / (complex a,double b) {return complex(a.x/b,a.y/b);} void FFT(int n,complex *a,int opt)
{
for (int i=; i<n; ++i)
if (i<r[i]) swap(a[i],a[r[i]]);
for (int k=; k<n; k<<=)
{
complex wn=complex(cos(pi/k),opt*sin(pi/k));
for (int i=; i<n; i+=k<<)
{
complex w=complex(,);
for (int j=; j<k; ++j,w=w*wn)
{
complex x=a[i+j], y=w*a[i+j+k];
a[i+j]=x+y; a[i+j+k]=x-y;
}
}
}
if (opt==-) for (int i=; i<n; ++i) a[i]=a[i]/n;
} void Manacher()
{
s[++tot]='('; s[++tot]='#';
for (int i=; i<n; ++i)
s[++tot]=st[i], s[++tot]='#';
s[++tot]=')';
int maxn=,mid=,x;
for (int i=; i<=tot; ++i)
{
if (i>maxn) x=;
else x=min(maxn-i+,len[mid*-i]);
while (s[i+x]==s[i-x]) x++;
len[i]=x;
if (i+x->maxn) maxn=i+x-, mid=i;
fun=(fun+len[i]/)%MOD;
}
} int main()
{
p[]=;
for (int i=; i<=; ++i)
p[i]=p[i-]*%MOD;
scanf("%s",st); n=strlen(st);
Manacher(); fn=;
while (fn<=n+n) fn<<=, l++;
for (int i=; i<fn; ++i)
r[i]=(r[i>>]>>) | ((i&)<<(l-));
for (int i=; i<n; ++i)
if (st[i]=='a') a[i].x=;
else b[i].x=;
FFT(fn,a,); FFT(fn,b,);
for (int i=; i<fn; ++i)
a[i]=a[i]*a[i], b[i]=b[i]*b[i];
FFT(fn,a,-); FFT(fn,b,-);
for (int i=; i<fn; ++i)
{
int x=(a[i].x+b[i].x+0.5);
x=(x+)>>;
Re=(Re+p[x]-)%MOD;
}
printf("%lld\n",(Re-fun+MOD)%MOD);
}
BZOJ3160:万径人踪灭(FFT,Manacher)的更多相关文章
-
BZOJ 3160: 万径人踪灭 [fft manacher]
3160: 万径人踪灭 题意:求一个序列有多少不连续的回文子序列 一开始zz了直接用\(2^{r_i}-1\) 总-回文子串 后者用manacher处理 前者,考虑回文有两种对称形式(以元素/缝隙作为 ...
-
P4199 万径人踪灭 FFT + manacher
\(\color{#0066ff}{ 题目描述 }\) \(\color{#0066ff}{输入格式}\) 一行,一个只包含a,b两种字符的字符串 \(\color{#0066ff}{输出格式}\) ...
-
BZOJ3160 万径人踪灭(FFT+manacher)
容易想到先统计回文串数量,这样就去掉了不连续的限制,变为统计回文序列数量. 显然以某个位置为对称轴的回文序列数量就是2其两边(包括自身)对称相等的位置数量-1.对称有啥性质?位置和相等.这不就是卷积嘛 ...
-
BZOJ3160 万径人踪灭 【fft + manacher】
题解 此题略神QAQ orz po神牛 由题我们知道我们要求出: 回文子序列数 - 连续回文子串数 我们记为ans1和ans2 ans2可以用马拉车轻松解出,这里就不赘述了 问题是ans1 我们设\( ...
-
BZOJ 3160: 万径人踪灭 FFT+快速幂+manacher
BZOJ 3160: 万径人踪灭 题目传送门 [题目大意] 给定一个长度为n的01串,求有多少个回文子序列? 回文子序列是指从原串中找出任意个,使得构成一个回文串,并且位置也是沿某一对称轴对称. 假如 ...
-
BZOJ3160 万径人踪灭 字符串 多项式 Manachar FFT
原文链接http://www.cnblogs.com/zhouzhendong/p/8810140.html 题目传送门 - BZOJ3160 题意 给你一个只含$a,b$的字符串,让你选择一个子序列 ...
-
Luogu4199 万径人踪灭 FFT、Manacher
传送门 先不考虑”不是连续的一段“这一个约束条件.可以知道:第$i$位与第$j$位相同,可以对第$\frac{i+j}{2}$位置上产生$1$的贡献(如果$i+j$为奇数表明它会对一条缝产生$1$的贡 ...
-
万径人踪灭(FFT+manacher)
传送门 这题--我觉得像我这样的菜鸡选手难以想出来-- 题目要求求出一些子序列,使得其关于某个位置是对称的,而且不能是连续一段,求这样的子序列的个数.这个直接求很困难,但是我们可以先求出所有关于某个位 ...
-
bzoj 3160: 万径人踪灭【FFT+manacher】
考虑正难则反,我们计算所有对称子序列个数,再减去连续的 这里减去连续的很简单,manacher即可 然后考虑总的,注意到关于一个中心对称的两点下标和相同(这样也能包含以空位为对称中心的方案),所以设f ...
随机推荐
-
infer 检验IOS项目
1.MAC安装infer: brew install infer 2.设置环境变量指向安装infer/bin下 3.source .bash_profile 4.命令 infer -- xcode ...
-
Oracle查询经典
.检索部门编号.部门名称.部门所在地及其每个部门的员工总数. select d.deptno,d.dname,d.loc,count(*) from emp e,dept d where e.dept ...
-
Webform——验证控件
验证控件一般是在注册的时候用到,是直接将JS代码封装到了控件里面,拉过来直接可以用,下面介绍一下主要用法: 1.CompareValidator:比较验证 常用属性:ControlToCompare ...
-
FineUI初学手册-部分JS整理
有人老找JS,我吧FineUI自己写的JS沾过来方便大家看看,在实现前端的时候更灵活 JS 实例 注释 控件 F.ready F.ready(function(){}); 就是ready 很多方法 ...
-
opendrive.com提供的免费网盘
opendrive.com是由以前freehao123给大家介绍的BOXSTr免费网络硬盘演变而来的,现在BOXSTr已经无法使用了.打开BOXSTr网站就会自动跳转到opendrive.com网站. ...
-
Swift - 属性观察者(willSet与didSet)
属性观察者,类似于触发器.用来监视属性的除初始化之外的属性值变化,当属性值发生改变时可以对此作出响应.有如下特点: 1,不仅可以在属性值改变后触发didSet,也可以在属性值改变前触发willSet. ...
-
前端笔记之Canvas
一.Canvas基本使用 Canvas是HTML5的画布,Canvas算是“不务正业”的面向对象大总结,将面向对象玩极致. 算法为王!就是说canvas你不会,但是算法好,不怕写业务,不怕代码量,只要 ...
-
【干货】使用SIFT取证工作站校验文件哈希----哈希一致则文件具备完整性
此实验来源于课程活动部分:第1单元:计算机取证基础 1.3活动和讨论 活动:* nix系统中文件的基本散列 注意:本博客更多的信息可能没有交代完善,有的人看不明白是因为,我知道,但是没有写出来.本 ...
-
Java核心技术及面试指南:视频列表
如下是本书相关内容的视频列表,会动态更新 第一章 1 视频1.1 JDK和JRE和JVM的区别,安装Java开发环境 1.1.1 第2页 2 视频1.2 编写第一个HelloWorld程序 ...
-
无法解析的外部命令gethostname
使用gethostname需要连接lib: #include <winsock2.h> #pragma comment(lib, "WS2_32.lib")