bzoj 3160 万径人踪灭 FFT

2023-11-10 21:41
文章标签 bzoj fft 万径 人踪 3160

本文主要是介绍bzoj 3160 万径人踪灭 FFT,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

万径人踪灭

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 1936  Solved: 1076
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Output

HINT

 

题目大意:给定一个由'a'和'b'构成的字符串,求不连续回文子序列的个数

首先回文一定是将字符串倍增 由于求的是不连续回文子序列的个数 因此我们可以求出总回文子序列的个数,然后减掉连续的

连续的就是回文子串 用Manacher算法可以O(n)求解

不连续的就有些难搞了

首先我们令f[i]表示以i为中心的对称字符对个数

比如s[]=$#a#b#a 那么s[4]='b' f[4]=2

那么对于每个中心i我们有(2^f[i])-1种方案 答案即Σ[1<=i<=n*2+1]((2^f[i])-1)

问题就是如何求出f[]数组

我们发现对f[i]有贡献的一对字符在原字符串数组中的位置之和一定是i

比如str+1="aba" 那么第一个字符和第三个字符对倍增后的字符串的第4个位置有贡献

那么显然有f[i]=(Σ[1<=j<=i-1]bool(str[j]==str[i-j]))+1>>1 括号里面是一个卷积的形式 可以用FFT进行求解

首先考虑'a'对答案的贡献 那么令'a'=1 'b'=0 求出卷积就是'a'的贡献

再考虑'b'对答案的贡献 令'a'=0 'b'=1 求出卷积就是'b'的贡献

两次贡献之和+1>>1就是f[]数组 代入之前的结论中即可出解

 

其中的数值是0和1代入

 

 1 #pragma GCC optimize(2)
 2 #pragma G++ optimize(2)
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<cstdio>
 8 
 9 #define mod 1000000007
10 #define ll long long
11 #define pi acos(-1)
12 #define N 300007
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
18     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 
22 int n,m,len,L;
23 ll ans;char ch[N];
24 int rev[N],bin[N],p[N];
25 struct comp
26 {
27     double r,v;
28     void init(){r=v=0;}
29     inline comp operator+(const comp &a){return(comp){r+a.r,v+a.v};}
30     inline comp operator-(const comp &a){return(comp){r-a.r,v-a.v};}
31     inline comp operator*(const comp &a){return(comp){r*a.r-v*a.v,r*a.v+v*a.r};}
32 }a[N],f[N],g[N];
33 
34 void manacher()
35 {
36     ch[0]='+',ch[len+1]='-';
37     int id,mx=0;
38     for(int i=1;i<=len;i++)
39     {
40         if(mx>i)p[i]=min(p[2*id-i],mx-i+1);
41         else p[i]=1;
42         while(ch[i+p[i]]==ch[i-p[i]])p[i]++;
43         if(i+p[i]-1>mx)mx=i+p[i]-1,id=i;
44         (ans-=p[i])%=mod;
45     }
46     mx=0;
47     for(int i=1;i<=len;i++)
48     {
49         if(mx>i)p[i]=min(mx-i,p[2*id-i]);
50         else p[i]=0;
51         while(ch[i+p[i]+1]==ch[i-p[i]])p[i]++;
52         if(i+p[i]>mx)mx=i+p[i],id=i;
53         (ans-=p[i])%=mod;
54     }
55 }
56 void FFT(comp *a,int f)
57 {
58     for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
59     for(int i=1;i<n;i<<=1)
60     {
61         comp wn=(comp){cos(pi/i),f*sin(pi/i)};
62         for (int j=0;j<n;j+=(i<<1))
63         {
64             comp w=(comp){1,0};
65             for (int k=0;k<i;k++,w=w*wn)
66             {
67                 comp x=a[j+k],y=w*a[j+k+i];
68                 a[j+k]=x+y,a[j+k+i]=x-y;
69             }
70         }
71     }
72     if(f==-1)for (int i=0;i<n;i++)a[i].r/=n;
73 }
74 int main()
75 {
76     bin[0]=1;for (int i=1;i<=100000;i++)bin[i]=(bin[i-1]<<1)%mod;
77     scanf("%s",ch+1);len=strlen(ch+1);
78     manacher();
79     m=2*(len-1);for(n=1;n<=m;n<<=1,L++);if(L)L--;
80     for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<L);
81     for (int i=0;i<len;i++)a[i].r=(ch[i+1]=='a')?1:0;
82     FFT(a,1);
83     for (int i=0;i<n;i++)f[i]=a[i]*a[i];
84     FFT(f,-1);
85     for (int i=0;i<n;i++)a[i].init();    
86     for (int i=0;i<len;i++)a[i].r=(ch[i+1]=='b')?1:0;
87     FFT(a,1);
88     for (int i=0;i<n;i++)g[i]=a[i]*a[i];
89     FFT(g,-1);
90     for (int i=0;i<n;i++)
91     {
92         int x=(int)(f[i].r+0.5)+(int)(g[i].r+0.5);
93         ans+=bin[(x+1)/2]-1;
94         ans%=mod;
95     }
96     printf("%lld",(ans+mod)%mod);
97 }

 

转载于:https://www.cnblogs.com/fengzhiyuan/p/8530811.html

这篇关于bzoj 3160 万径人踪灭 FFT的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/385428

相关文章

【数字信号处理】一文讲清FFT(快速傅里叶变换)

目录 快速傅里叶变换(Fast Fourier Transform,FFT)FFT的背景快速傅里叶变换(Fast Fourier Transform,FFT)DFT的数学表达实际计算重要性和应用频谱泄露、频谱混叠奈奎斯特采样定理参考链接 快速傅里叶变换(Fast Fourier Transform,FFT) FFT的背景 1、为什么要时域→频域频率?50Hz+频率120Hz

【BZOJ】1324 Exca王者之剑 最大权独立集

传送门:【BZOJ】1324  Exca王者之剑 题目分析:赤裸裸的最大权独立集。。。最小割解决 代码如下: #include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std ;#define REP( i , a , b ) for ( int

【BZOJ】1026: [SCOI2009]windy数 数位DP

传送门:【BZOJ】1026: [SCOI2009]windy数 题目分析:数位DP水题。 代码如下: #include <stdio.h>#include <cstring>#include <algorithm>#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )#define For( i ,

【BZOJ】2152: 聪聪可可 点分治

传送门:【BZOJ】2152: 聪聪可可 题目分析:记录权值和%3的路径的个数。。。然后去重。。没了。。 代码如下: #include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std ;typedef lo

【BNU】40719 Arithmetic Progressions【分块+FFT】

传送门:【BNU】40719 Arithmetic Progressions 题目分析: 用分块+FFT强行AC了这题…… 之前一直TLE……然后改了好久把姿势改的优美点了……终于过了…… 大概思路是:我们考虑分块,假设每一块的大小为S,一共分了B块然后我们分两种情况讨论: 1.第二个数在第i块,第一个数在(1~i-1)块内,第三个数在(i+1~B)块内。 2.至少两个数在同一块内。

【HDU】5197 DZY Loves Orzing 【FFT启发式合并】

传送门:【HDU】5197 DZY Loves Orzing 题目分析: 首先申明,我不会 dp dp方程= =……这个东西给队友找出来了,然后我就是套这个方程做题的Qrz…… 对于这题,因为 n2 n^2个数互不相同,所以每一列都可以单独考虑。设 dpni dp_ni表示长度为 n n的排列,能恰好看见ii个人的方案数,根据队友的发现, dpni dp_ni就等于 |sni| |s_ni|

【ZOJ】3874 Permutation Graph 【FFT+CDQ分治】

传送门:【ZOJ】3874 Permutation Graph 题目分析: 容易知道一个个连通块内部的标号都是连续的,否则一定会有另一个连通块向这个连通块建边,或者这个连通块向另一个连通块建边。而且从左到右左边的连通块内最大的标号小于右边连通块内最小的标号。 然后我们可以构造dp方程: dp[n]=n!−i!∗dp[n−i] \qquad \qquad dp[n] = n! - i! *

【SPOJ】Triple Sums【FFT】

传送门:【SPOJ】Triple Sums 题目分析: 首先我们不考虑 i<j<k i<j<k这个条件,构造多项式: Y=∑xai \qquad\qquad\qquad Y = \sum x^{a_i} 那么 ai+aj+ak=S ai+aj+ak=S的个数即 xai+aj+ak=S x^{a_i+a_j+a_k=S}的个数,等价于 Y3中xS Y^3中x^S的系数。 然后我们考虑容斥

【BNU】33943 Super Rooks on Chessboard 【FFT】

【BNU】33943 Super Rooks on Chessboard UVA上的题,然而我怎么会蠢到去UVA呢!(其实是百度首先跳出来的是BNU → \to_ → \to) 题目分析: 设 numx numx为 N N个车没有覆盖的行数,numynumy为 N N个车没有覆盖的列数。 首先我们考虑没有主对角线覆盖这一条件时,总共的没有被覆盖的面积就是numx∗numynumx \ast

【HDU】4609 3-idiots 【FFT】

传送门:【HDU】4609 3-idiots 题目分析: 我们考虑两边长度之和为 n n的方案数,设num[x]num[x]为长度为 x x的个数,那么∑nx=1num[n−x]∗num[x]\sum_{x=1}^{n}{num[n-x]*num[x]} 即两边长度之和为 n n的方案数。容易发现这这正是卷积!然后我们就可以愉快的用FFTFFT预处理出所有的两边长度之和为i的方案数。 FFT