题解
此题略神QAQ
orz po神牛
由题我们知道我们要求出:
回文子序列数 - 连续回文子串数
我们记为ans1和ans2
ans2可以用马拉车轻松解出,这里就不赘述了
问题是ans1
我们设\(f[i]\)表示以i位置为中心的对称的字符对数,那么i位置产生的回文子序列数 = \(2^{f[i]} - 1\)
如何求?
由对称的性质,以i为对称中心的两点\(a,b\)满足\(a+b=2*i\)
我们可以设一个这样的序列:
\(c[n]\)表示以\(n/2\)位置为对称点的对称点对数【n/2若不为整数则对称中心是字符间隙】
那么有:
\(c[n] = \sum a[k]*a[n - k]\),a[k]表示k位置的字符,*运算满足当且仅当两者字符相等时为1,否则为0
我们只需要求两次fft:
①'a'位置赋值0,'b'位置赋值1,求\(c[n] = \sum a[k]*b[n - k]\)
②'a'位置赋值1,'b'位置赋值0,求\(c[n] = \sum a[k]*b[n - k]\)
两次之和即为所求,再跑一次DFT即可【我也不知道为什么可以这样,抄po神的代码】
【讲道理分开来求,然后相加应该也行】
最后ans = ans1 - ans2
真心心累。。。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<complex>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 800005,maxm = 200005,INF = 1000000000,P = 1000000007;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}
return out * flag;
}
char s[maxm],t[maxm];
int RL[maxm],n;
LL ans1,ans2,F,power[maxn];
void manacher(){
s[0] = '*';
int pos = 1,mr = 1; RL[1] = 1;
for (int i = 2; i < n; i++){
if (i <= mr) RL[i] = min(RL[2 * pos - i],mr - i + 1);
else RL[i] = 1;
while (s[i + RL[i]] == s[i - RL[i]]) RL[i]++;
if (i + RL[i] - 1 >= mr) mr = i + RL[i] - 1,pos = i;
}
}
const double pi = acos(-1);
typedef complex<double> E;
E a[maxn],b[maxn];
int m,L,R[maxn];
void fft(E* a,int f){
for (int i = 0; i < n; i++) if (i < R[i]) swap(a[i],a[R[i]]);
for (int i = 1; i < n; i <<= 1){
E wn(cos(pi / i),f * sin(pi / i));
for (int j = 0; j < n; j += (i << 1)){
E w(1,0);
for (int k = 0; k < i; k++,w *= wn){
E x = a[j + k],y = w * a[j + k + i];
a[j + k] = x + y; a[j + k + i] = x - y;
}
}
}
if (f == -1) for (int i = 0; i < n; i++) a[i] /= n;
}
int main(){
scanf("%s",t + 1); int len = strlen(t + 1);
for (int i = 1; i <= len; i++) s[++n] = '#',s[++n] = t[i]; s[++n] = '#';
manacher();
for (int i = 1; i <= n; i++) ans2 = (ans2 + (RL[i] >> 1)) % P;
//cout<<ans2<<endl;
power[0] = 1; for (int i = 1; i <= n; i++) power[i] = (power[i - 1] << 1) % P;
n = len;
m = n << 1; for (n = 1; n <= m; n <<= 1) L++;
for (int i = 0; i < n; i++) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
for (int i = 1; i <= len; i++) a[i] = (t[i] == 'a');
fft(a,1);
for (int i = 0; i < n; i++) b[i] = a[i] * a[i];
memset(a,0,sizeof(a));
for (int i = 1; i <= len; i++) a[i] = (t[i] == 'b');
fft(a,1);
for (int i = 0; i < n; i++) b[i] += a[i] * a[i];
fft(b,-1);
for (int i = 1; i < n; i++){
F = (LL)(b[i].real() + 0.5);
ans1 = (ans1 + power[F + 1 >> 1] - 1) % P;
}
//cout<<ans1<<endl;
printf("%lld\n",((ans1 - ans2) % P + P ) % P);
return 0;
}
BZOJ3160 万径人踪灭 【fft + manacher】的更多相关文章
-
BZOJ3160:万径人踪灭(FFT,Manacher)
Solution $ans=$回文子序列$-$回文子串的数目. 后者可以用$manacher$直接求. 前者设$f[i]$表示以$i$为中心的对称的字母对数. 那么回文子序列的数量也就是$\sum_{ ...
-
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.对称有啥性质?位置和相等.这不就是卷积嘛 ...
-
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 ...
随机推荐
-
c#中如何获取listbox中选中值的问题
StringBuilder ConponPerson = new StringBuilder(); for (int i = 0; i < lb_tzs.Items.Cou ...
-
【温故而知新-Javascript】使用Web存储
Web存储允许我们在浏览器里保存简单的键/值数据.Web存储和cookie很相似,但它有着更好的实现方式,能保存的数据量也很大.这两种类型共享相同的机制,但是被保存数据的可见性和寿命存在区别. PS: ...
-
如何让chrome始终运行插件
使用chrome可能有时候会拦截比如阿里旺旺和腾讯等的登录插件,那么怎么才始终允许,而不需要每次确认呢.下面. 1. 打开Chrome浏览器. 在地址栏中输入 chrome://plugins 回车 ...
-
C# <;%@ Register %>;指令
将别名与命名空间及类名关联起来,以便在自定义服务器控件语法中使用简明的表示法. <%@ register tagprefix="tagprefix" namespace=&q ...
-
Excel 窗体控件属性
常规 AutoLoad (Excel) 打开工作簿时是否加载控件.(如果是 ActiveX 控件,则忽略.) Enabled(表单) 控件是否可以接收焦点并响应用户生成的事件. Locked( ...
-
【ROW_NUMBER 函数(Transact-SQL)】
[ROW_NUMBER 函数(Transact-SQL)]返回结果集分区内行的序列号,每个分区的第一行从 1 开始. 注释: ROW_NUMBER() OVER (PARTITION BY COL1 ...
-
Cocos移植到Android-使用Eclipse交叉编译打包
如果对命令行望而生畏,我们可以借助于安装有ADT插件的Eclipse工具实现交叉编译.使用Eclipse进行交叉编译,首先需要将要编译的工程导入到Eclipse的Workspace中,Workspac ...
-
php学习小技巧
1.print_r可打印数组 <?php echo '<p class="ajax">This paragraph was loaded with AJAX.&l ...
-
使用git上传项目到github
来自: http://www.cnblogs.com/specter45/p/github.html GitHub是基于git实现的代码托管.git是目前最好用的版本控制系统了,非常受欢迎,比之svn ...
-
JAVA核心技术I---JAVA基础知识(列表List)
一:List了解 (一)List:列表 –有序的Collection –允许重复元素 –{,,,{,},,} (二)List:主要实现 同步/非同步:针对线程而言 –ArrayList(非同步的) – ...