icontofig | 发布于 2019-10-12 15:07:44 | 阅读量 118 | NTT 数学 组合数 生成函数
发布于 2019-10-12 15:07:44 | NTT 数学 组合数 生成函数
HAOI2018 染色 NTT 组合数 生成函数
题解 首先声明……其实我们的答案跟Wi'>WiWiW_i没太大关系,这一部分只需要在最后的时候对应乘上即可,此题最核心的部分是计算选择了i种颜色的方案数。 首先我们来看如果我们选择了i种颜色使它们恰好出现了S次,那么选择颜色种类的方案数即为Cmi'>CimCmiC_m^i,然后我们去用这i个颜色涂这n个位置的时候,实际上就是一个可重排列的计算数,方案总数为n!(S!)i∗(n−i∗S)!'>n!(S!)i∗(n−i∗S)!n!(S!)i∗(n−i∗S)!\frac{n!}{{(S!)}^i * (n-i*S
继续阅读
icontofig | 发布于 2019-10-12 15:06:43 | 阅读量 121 | NTT 数学 组合数
发布于 2019-10-12 15:06:43 | NTT 数学 组合数
#include <bits/stdc++.h> using namespace std; int n,m,s; const int maxm = 1e5+5; const int maxn = 1e7+5; typedef long long ll; const ll mod = 1004535809; ll fac[maxn],inv[maxn],w[maxm],f[maxm<<2],finv[maxn]; ll b[maxm<<2]; int rev[maxm<<2]; void init(int x){ fac[0] = fac[
继续阅读
icontofig | 发布于 2019-09-26 19:59:05 | 阅读量 510 | 生成函数 NTT
发布于 2019-09-26 19:59:05 | 生成函数 NTT
luogu P3321 BZOJ 3992 [SDOI2015]序列统计 NTT + 生成函数 + 快速幂
题解如果你曾经经过大量的FFT/NTT的生成函数训练,应该一眼能够看出这道题一定是个多项式卷积用NTT优化…… 如果是相加的话,我们可以直接设多项式S = Σaixi,(生成函数在这)其中ai表示数字i出现过多少次。 如果我们是选2个数的话,对于每一个和的方案数,很明显就是将S卷上S,然后取对应多项式项的系数即为方案数。 因为这个题是乘积,而且对于乘积还有对质数m取模操作,所以我们不能简单的按照上面的方法进行生成函数构造。 如何解决乘积问题呢? 我们知道多项式FFT/NTT都是建立在指数(下标)相加的基础上(也就是普通的多项式乘法的法则)进行的,所以我们想能不能把乘积变成加法,这样就可以按照经
继续阅读