BZOJ3160 万径人踪灭 【fft + manacher】

时间:2022-05-14 13:15:32

BZOJ3160 万径人踪灭  【fft + manacher】

BZOJ3160 万径人踪灭  【fft + manacher】

BZOJ3160 万径人踪灭  【fft + manacher】

BZOJ3160 万径人踪灭  【fft + manacher】

题解

此题略神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】的更多相关文章

  1. BZOJ3160&colon;万径人踪灭&lpar;FFT&comma;Manacher&rpar;

    Solution $ans=$回文子序列$-$回文子串的数目. 后者可以用$manacher$直接求. 前者设$f[i]$表示以$i$为中心的对称的字母对数. 那么回文子序列的数量也就是$\sum_{ ...

  2. BZOJ 3160&colon; 万径人踪灭 &lbrack;fft manacher&rsqb;

    3160: 万径人踪灭 题意:求一个序列有多少不连续的回文子序列 一开始zz了直接用\(2^{r_i}-1\) 总-回文子串 后者用manacher处理 前者,考虑回文有两种对称形式(以元素/缝隙作为 ...

  3. P4199 万径人踪灭 FFT &plus; manacher

    \(\color{#0066ff}{ 题目描述 }\) \(\color{#0066ff}{输入格式}\) 一行,一个只包含a,b两种字符的字符串 \(\color{#0066ff}{输出格式}\) ...

  4. BZOJ3160 万径人踪灭(FFT&plus;manacher)

    容易想到先统计回文串数量,这样就去掉了不连续的限制,变为统计回文序列数量. 显然以某个位置为对称轴的回文序列数量就是2其两边(包括自身)对称相等的位置数量-1.对称有啥性质?位置和相等.这不就是卷积嘛 ...

  5. BZOJ 3160&colon; 万径人踪灭 FFT&plus;快速幂&plus;manacher

    BZOJ 3160: 万径人踪灭 题目传送门 [题目大意] 给定一个长度为n的01串,求有多少个回文子序列? 回文子序列是指从原串中找出任意个,使得构成一个回文串,并且位置也是沿某一对称轴对称. 假如 ...

  6. BZOJ3160 万径人踪灭 字符串 多项式 Manachar FFT

    原文链接http://www.cnblogs.com/zhouzhendong/p/8810140.html 题目传送门 - BZOJ3160 题意 给你一个只含$a,b$的字符串,让你选择一个子序列 ...

  7. Luogu4199 万径人踪灭 FFT、Manacher

    传送门 先不考虑”不是连续的一段“这一个约束条件.可以知道:第$i$位与第$j$位相同,可以对第$\frac{i+j}{2}$位置上产生$1$的贡献(如果$i+j$为奇数表明它会对一条缝产生$1$的贡 ...

  8. 万径人踪灭(FFT&plus;manacher)

    传送门 这题--我觉得像我这样的菜鸡选手难以想出来-- 题目要求求出一些子序列,使得其关于某个位置是对称的,而且不能是连续一段,求这样的子序列的个数.这个直接求很困难,但是我们可以先求出所有关于某个位 ...

  9. bzoj 3160&colon; 万径人踪灭【FFT&plus;manacher】

    考虑正难则反,我们计算所有对称子序列个数,再减去连续的 这里减去连续的很简单,manacher即可 然后考虑总的,注意到关于一个中心对称的两点下标和相同(这样也能包含以空位为对称中心的方案),所以设f ...

随机推荐

  1. c&num;中如何获取listbox中选中值的问题

    StringBuilder ConponPerson = new StringBuilder();            for (int i = 0; i < lb_tzs.Items.Cou ...

  2. 【温故而知新-Javascript】使用Web存储

    Web存储允许我们在浏览器里保存简单的键/值数据.Web存储和cookie很相似,但它有着更好的实现方式,能保存的数据量也很大.这两种类型共享相同的机制,但是被保存数据的可见性和寿命存在区别. PS: ...

  3. 如何让chrome始终运行插件

    使用chrome可能有时候会拦截比如阿里旺旺和腾讯等的登录插件,那么怎么才始终允许,而不需要每次确认呢.下面. 1. 打开Chrome浏览器. 在地址栏中输入 chrome://plugins 回车 ...

  4. C&num; &lt&semi;&percnt;&commat; Register &percnt;&gt&semi;指令

    将别名与命名空间及类名关联起来,以便在自定义服务器控件语法中使用简明的表示法. <%@ register tagprefix="tagprefix" namespace=&q ...

  5. Excel 窗体控件属性

    常规 AutoLoad   (Excel) 打开工作簿时是否加载控件.(如果是 ActiveX   控件,则忽略.) Enabled(表单) 控件是否可以接收焦点并响应用户生成的事件. Locked( ...

  6. 【ROW&lowbar;NUMBER 函数&lpar;Transact-SQL&rpar;】

    [ROW_NUMBER 函数(Transact-SQL)]返回结果集分区内行的序列号,每个分区的第一行从 1 开始. 注释: ROW_NUMBER() OVER (PARTITION BY COL1 ...

  7. Cocos移植到Android-使用Eclipse交叉编译打包

    如果对命令行望而生畏,我们可以借助于安装有ADT插件的Eclipse工具实现交叉编译.使用Eclipse进行交叉编译,首先需要将要编译的工程导入到Eclipse的Workspace中,Workspac ...

  8. php学习小技巧

    1.print_r可打印数组 <?php echo '<p class="ajax">This paragraph was loaded with AJAX.&l ...

  9. 使用git上传项目到github

    来自: http://www.cnblogs.com/specter45/p/github.html GitHub是基于git实现的代码托管.git是目前最好用的版本控制系统了,非常受欢迎,比之svn ...

  10. JAVA核心技术I---JAVA基础知识(列表List)

    一:List了解 (一)List:列表 –有序的Collection –允许重复元素 –{,,,{,},,} (二)List:主要实现 同步/非同步:针对线程而言 –ArrayList(非同步的) – ...