Tag-生成函数

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

 2019-10-12 15:07:44 |  0 Comments  |  NTT 数学 组合数 生成函数

HAOI2018 染色 NTT 组合数 生成函数

图片标题

题解

首先声明……其实我们的答案跟Wi没太大关系,这一部分只需要在最后的时候对应乘上即可,此题最核心的部分是计算选择了i种颜色的方案数。
首先我们来看如果我们选择了i种颜色使它们恰好出现了S次,那么选择颜色种类的方案数即为Cmi,然后我们去用这i个颜色涂这n个位置的时候,实际上就是一个可重排列的计算数,方案总数为n!(S!)i(niS)!,然后剩下的位置任意涂色,一共还剩n-i*S个位置,每个位置有m-i种颜色选择,所以方案数为(mi)niS
我们记fi=Cmin!(S!)i(niS)!(mi)niS
然而这并不是恰好有i种颜色恰好都出现k次。实际上在我们在后面自由涂色的时候,我们依旧有可能会将一种颜色涂成恰好出现k次。
So……这时候我们就用到容斥原理了。假设ansi为恰好i种颜色都恰好出现k次,由容斥原理有:
ansi=j=imin(m,n/S)(1)jiCjifjj

 2019-09-26 19:59:05 |  0 Comments  |  生成函数 NTT

luogu P3321 BZOJ 3992 [SDOI2015]序列统计 NTT + 生成函数 + 快速幂

题解

如果你曾经经过大量的FFT/NTT的生成函数训练,应该一眼能够看出这道题一定是个多项式卷积用NTT优化……

如果是相加的话,我们可以直接设多项式S = Σaixi,(生成函数在这)其中ai表示数字i出现过多少次。

如果我们是选2个数的话,对于每一个和的方案数,很明显就是将S卷上S,然后取对应多项式项的系数即为方案数。

因为这个题是乘积,而且对于乘积还有对质数m取模操作,所以我们不能简单的按照上面的方法进行生成函数构造。

如何解决乘积问题呢?

我们知道多项式FFT/NTT都是建立在指数(下标)相加的基础上(也就是普通的多项式乘法的法则)进行的,所以我们想能不能把乘积变成加法,这样就可以按照经典套路进行生成函数构造了。

想了一下,取对数貌似可以把乘法变成加法来算了……

但是因为此处还是对质数m取模之后结果的统计,而且NTT也不支持浮点数,所以我们需要考虑在模意义下的对数,也就是离散模对数。

如何处理离散模对数呢……这里如果不了解的话就需要补一下基础的数论知识了。

这里我们需要求m的原根,求法也非常简单,直接暴力枚举的每个数,看对于每个质数pi | (m-1),是否g的(m-1)/pi次方mod m等于1,如果等于则说明不是原根,否则说明是原根,原根通常非常小,所以不用担心会在处理原根的时候TLE。

运用原根,我们可以把每个数在mod m意义下的离散模对数求出来,然后就变成正常的多项式卷积啦!

于是这个时候我们就可以用NTT来做啦。

但是由于要选N次,而N的数据范围到了1e9次,所以我们不能直接暴力NTT,要用快速幂的思想对多项式进行快速幂形式的卷积操作。

这里要注意每一次卷积完成的时候(IDNT之后),我们只是正常的进行了一次多项式卷积,统计答案的时候还是有问题的,因为指数并不能取模,所以每一卷积,都会有答案落在[m-1,2*m-2]上,我们要把这一区域上的答案对应地加到前面[0,m-2]上(对应了题目中的乘积取模操作)。

总时间复杂度为O(nlog2n)。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxm = 16005;
typedef long long ll;
const ll gf = 3;
int n,m,x,s;
ll tmp;
int sq;
const ll mod = 1004535809;
ll f
 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){};
Title - Artist
0:00