Tag-FFT

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-09-22 21:13:56 |  0 Comments  |  FFT 字符串 生成函数

BZOJ 3160 万径人踪灭 FFT + 回文自动机 + 生成函数

题目大意

 给定一个字符集仅含a和b的字符串s,求字符串中不连续的回文子序列个数mod 1000000007的值。

题解

如果是连续的回文子序列,也就是回文串,那就很好求了,直接运用Manacher算法就可以了。

但是这题是让算所有的不连续的回文子序列……

然而这个是没法直接算出来的……

所以我们反过来想,我们可以把所有回文子序列的数量求出来,然后减去回文子串的数量,就是不连续的回文子序列的数量。

上面说了,如果是回文子串的数量,可以直接用Manacher算法算出来。

所以现在我们考虑的就是全体回文子序列的数量该怎么算。

对一个回文子序列,一定有一个中心,假设两个对应字符位置分别为x,y,那么,中心的位置一定是(x+y)/2。

我们可以将那个/2拿掉,这样算出来的新的中心位置也是唯一确定的,也就是和本质的回文中心位置一一对应。

对于一个位置,假设有x对(两个字符在同一位置也算一对)对应字符确定的中心位置在此位置,那么一定有以此位置为回文中心的回文子序列个数为2^x - 1。

如果我们直接暴力求出,那么复杂度是O(n2)的,n是100000的数据是吃不消的。

注意到字符集只含两个字符,再观察对应字符确定的新的中心位置的计算公式(pos = x + y),我们可以对于字符a和字符b分别构造生成函数:

假设我们当前对字符c进行计算,则有生成函数f(x) = Σ((s[i] == c) ? 1 : 0) * xi

可以看出,对字符c,有多少对对应字符的中心位置确定在所有的位置的数量与f(x)对f(x)的卷积在对应位置的系数值是有关系的(其实是一个近似于/2的关系,不过涉及到要讨论位置的奇偶,这里不再赘述)。

卷积可以所以相当于我们对字符a和b分别构造生成函数,分别进行FFT,然后对于每一个位置,将两个FFT算出的结果相加,然后+1,再除以2,即为当前位置为中心位置的对应字符对数(这里+1再/2(整除)是一个巧妙地避开对两个对应字符在相同位置(也就是说这一对字符完全就是一个字符)的讨论的做法,请自行理解)。之后按照上面的公式处理以下即可。

这样我们就求出了所有回文子序列的个数。

至于回文子串的个数,可以直接用Manacher算法来解。

但是……

博主不会Manacher……而且也懒得学……

可是我会PAM(回文自动机)啊!回文自动机可比Manacher好用多了(个人观点不代表官方意见)!

回文自动机里面的cnt[i]

 2019-09-21 15:29:50 |  0 Comments  |  FFT 生成函数

The Preliminary Contest for ICPC Asia Shanghai 2019 C.Triple FFT + 生成函数

题目大意

给定一个正整数n,有三个数组A,B,C,每个数组有n个数,求问有多少个三元组(i,j,k)满足|Ai-Bj|≤Ck,|Ck-Bj|≤Ai,|Ai-Ck|≤Bj

题解

首先我们发现,其实三元组满足的条件其实非常像三角形的构成条件,所以我们可以叙述成

“最小值 + 中间值 ≤ 最大值”

满足这样的三元组个数。

官方题解是正着算的,然后还有什么去重什么麻烦的东西,看起来令人头大……

所以我们为何不反过来算呢?

首先所有的取法总数是n3,然后我们只需要计算以下不满足的三元组总数即可了。

但是怎么做?

大概的思路就是对于某一个数组中的所有数,我们对每一个进行枚举,把当前枚举的数作为三元组的最大值,看剩下两个数组中有多少个二元组满足两个数加起来小于当前这个数。

具体的思路就是这样,但是暴力算时间复杂度会崩,是O(n3)的。

我们可以把所有二元组的和都预处理出来,用桶计数,表示当前二元组的和为i的组数有多少个。然后我们对要枚举的数列先从小到大排序,再进行枚举,用前缀和的思想找上述的不满足条件的二元组的个数即可,这样的做法是O(n2)的。

但是还不够,因为n最大是1e5。

这时候我们就要应用生成函数的思想,对于每一个数y,把y放在x的指数上,y在这个数组中出现的次数作为这一项的系数。这样任意两项乘在一起就相当于一个加和。

我们要算所有二元组的加和,用上面的生成函数的思想,就可以把暴力转化成为一个普通卷积,而卷积可以用FFT来加速。于是就可以优化为O(nlogn)。

整体需要3次DFT和3次IDFT。

然后按照上述方法前缀和枚举即可。

but……因为FFT是用桶的思路,所以每一次FFT都是用最大值代入的时间复杂度中的n,而且FFT常数巨大,这就导致我们直接FFT会超时。

我们关注到题目中N > 1000的数据组最多只有20组,于是我们可以分数据范围,n<1000 的直接n2暴力,n > 1000的使用FFT。这样就不会超时了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
const double  pi = acos(-1.0);
struct comp{
	double r,i;
	comp(double a = 0,double b = 0):r(a),i(b){};
 2019-07-02 10:25:10 |  0 Comments  |  FFT

BZOJ 3527 [ZJOI2014]力 FFT模板题

题解

就是把qj除掉,然后可以发现是裸的两个卷积形式,直接上FFT就可以。

这个博客写的非常好,我个人就比较渣了QAQ https://blog.csdn.net/qq_33929112/article/details/54590319

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const int maxn = (1<<18) + 5;
const int INF = 1e9;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = (num << 1) + (num << 3) + c - '0';
	return (flag ? -1 : 1) * num;
}
struct comp{
	double x,y;
	comp(double a = 0,double b = 0):x(a),y(b){};
};
comp operator + (comp a,comp b){return comp(a.x + b.x,a.y + b.y);}
comp operator - (comp a,comp b){return comp(a.x - b.x,a.y - b.y);}
comp operator * (comp a,comp b){return comp(a.x*b.x - a.y * b.y,a.x * b.y + a.y * b.x);}
comp conj(comp a){
	return comp(a.x,-a.y);
}
struct FFT{
	int n,rev[maxn];
	void get_inv(int bit){
		n = 1;int k = 0;
        while(n < bit) n <<= 1,k++;
        
 2017-04-01 10:00:46 |  0 Comments  |  FFT

FFT模板 【UOJ】模板题库 多项式乘法

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <complex>
using namespace std;
const int maxn = 3e5+5;
const double pi = acos(-1);
int n = 0;
int n1,n2;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = num * 10 + c - '0';
	return (flag ? -1 : 1) * num;
}
struct FFT{
	complex<double>omega[maxn],iomega[maxn];
	void init(const int n){
		for(int i = 0;i < n;++i){
			omega[i] = complex<double>(cos(2*pi*i/n),sin(2*pi*i/n));
			iomega[i] = conj(omega[i]);
		}
	}
	void trans(complex<double> *a,const int n,const complex<double> *omega){
		int k = 0;
		while((1 << k) < n)k++;
		for(int i = 0;i < n;++i){
			int t = 0;
			for(int j = 0;j < k;j++)if(i&(1 << j))t |= (1 << (k-j-1));
			if(i < t)swap(a[i],a[t]);
		}
		for(int l = 2;l <= n;l *= 2){
			int m = l / 2;
			for(co
Title - Artist
0:00