组合数学

总结 , 评论

组合数学

Basic Formula

容斥定义

证明:

另一个证明同理

斯特林反演：

证明：

已知

另一个证明同理

应用：

第一类斯特林数求行(OGF形式)

已知 求 将 翻转一下再卷上 再除以 即可

对应到第一类斯特林数就是 。使用倍增解决

第一类斯特林数求列（EGF形式）

有且仅有一个圆排列的 为 所以恰好 个有标号圆排列的 为

第一类斯特林数是无标号的所以其对应的 还要除以 尝试从结论倒推能推出什么：把所有 看作 得到 两边同时取所有项并乘上一个 的系数 右边

于是倒着推也是可以推出答案式子的

注意ln之后常数项为 不能qpow的时候直接return exp(ln(f)*k)，要提前去掉末尾

第二类斯特林数求行（OGF形式）

第二类斯特林数求列（EGF形式）

也可以用和第一类求列相类似的推导，注意 常数项系数为 ，qpow时同第一类求列都要特殊处理

CF 932 E

HEOI2016 求和

（可优化到线性，见 200415 T3）

FJOI2016 建筑师

个数里选若干个组成 个环，剩下的再组成 个环

即一共组成 个环每种组成 个环的方式被算了 次

P4827 Crash 的文明世界

令

BZOJ3622 已经没有什么好害怕的了

表示恰有 组 比 多的方案数 表示至少 组 比 多的方案数 表示前 小的数，已经配了 对 现在左边是否还有没配对的 的方案数

对于

对于

剩下的随便配对即

上面的dp是错误的，其并不能算出至少 对的方案数因为会有一些时候的”前缀未配对B个数”大于1

比如配对 时配 对时会算出 实际上是

应记录对于每个 有多少个 小于它,记为 则记 为前 个点，硬点了 个连比他小的边，剩下的不连，的方案数。转移就是

注意到这个转移恰好不重不漏的计算了至少 个大到小的边的情况，至于剩下的 条边可以任意连，答案就是

P4002 生成树计数

构造 则

即得 已知一个函数各项系数 求 ： #### 如何快速求 ：

$$ 然后考虑构造一个函数

$$

另解：

令 表示 在prufer序列前 项的出现次数，有

考虑其组合意义即对于一个prufer序列我们在它后面再添上 使得每个数恰好出现其度数次，然后我们可以把 看成对 的每个颜色的 个位置染 次色，且这 次染色可以染到同一位置的方案数。然后上面式子的意思就是一共有且仅有一个数 被染了 次，其他的都被染了 次，问最后的方案乘上改方案对应的权值（ ）的值

注意到 比较小可以枚举这 次染色一共染了几个不同的位置，比如染了 个指定的位置时方案数即为

然后 表示数字 都只染了 次，一共占了prufer序列的 个位置时的只考虑染了色的位置时的总权值

表示数字 中有且仅有一个数染了 次（其余都是染 次）一共占了prufer序列的 个位置时的只考虑染了色的位置时的总权值

转移时考虑有没有染到后 个中对应的那个位置得到

令

注意初值是

然后分治ntt的写法可以不管什么看上去是 这样的东西不知道怎么推导

直接计算两边两个关于 的多项式，一个 表示有且仅有一个数字染了 次的方案，一个 表示全部都只染了 次，然后直接

即可（注意只用最后 项，最后 即剩下的 个空格任意填 ，每填一个 则权值多乘上一个 ）

（ ）

P3711 仓鼠的数学题

翻转后卷积即可

CF 932 E严格加强

求 。其中 是一个关于 的 次多项式

先把 转成下降幂形式

如何转次幂为下降幂？

令 ，有

因为 也是 次多项式 只需多点求值求出所有 再除以 卷上 即可 （注意顺序）

2019 江苏省队集训D1T3 魔法咒语

已知 且 求 要求线性

这个 只和 有关

下降幂多项式乘法

其点值的 为

即直接把 卷上 即可得到点值的

两个下降幂的点值的 对应项相乘再乘上多余的一个 以去掉两个同时作为 的分母上的 即可得到答案的点值的

从点值 求原下降幂多项式直接除以 即乘上 即可

P4389 付公主的背包

直接调和级数一样做即可

下降幂转次幂

下降幂转点值的 直接乘上

再上个快速插值

快速插值

使用多点求值得到每个 的

然后每一项的常数项即为 再乘上 即return tr[lk]*solve(l,mid)+tr[rk]*solve(mid+1,r);

但这题可能会 。。。 跑了36s

注意到 所以

WC2019 数树

首先有

type=0

直接求并大小

type=1

注意到有一个容斥式子

证明：

右式

然后带入 无脑推式子

其中 表示含有边集 的树有多少种

若 形成 个连通块 则

证明可以直接用行列式，这里写另一种

把每个已经确定的连通块看成一个点，然后直接用prufer序列，但是每一个连出去的边都有 种连法,令prufer序列第 个点为 ,令第 个点在prufer序列里出现 次，那么其度数为 ，得到

若有 条边，则连通块个数

令 相当于每个大小为 的连通块对答案有 的贡献

设 表示以 为根，包含 的连通块大小为 时，子树内所有情况下的答案（且不包含本身所在的连通块）

得到

转移是

初值

现在已经可以 求解，考虑再优化

把 看成是一个集合幂级数，则

令

则

再令 即可得到

即可 dp了

type=2

其中 是两个树都包含 这个边集的方案数，且 （因为两棵树不等价，第一棵可以任选 中的一棵，第二棵也是）

所以带入得到

$$

$$

对于一个确定点数为 的树，共有 种形式

把 个点分成 个有标号且大小分别为 的连通块的方案是

则把 个点分成 个无标号且大小分别为 的连通块的方案是

令一种理解上式的方法：

一个大小为 的树的权值为

一个森林的权值为里面所有树的权值之积

求所有森林的权值之和

所以直接 exp 就行了

CodeChef PSUM

NTT卷积优化dp即可

BZOJ5093 图的价值

$$

$$

算出第二类斯特林数后直接for一遍即可

分布

方差 和 的关系

伯努利分布

一个变量 有 的概率为 ， 的概率为

则

二项式分布

二项分布是 个独立的是/非试验中成功的次数的离散概率分布，其中每次试验的成功概率为

注：以下记

由定义可得每次成功与否是独立的，可得

或者组合意义下证明

有点难搞，因为 根据上面的类似推一下

所以

同时类似的可以得到

UOJ269 如何优雅地求和

这道16年的题给了点值，现在看上去很明显，实际上应该要能自己想出来最重要的一步即转成下降幂

设

注意点值转下降幂的公式中，哪里要除以阶乘哪里乘阶乘要想清楚!

cf961G Partitions

$$

$$

然后直接做即可，也可以用线性筛去掉快速幂的 （注意 是0 base的）（实际上第一行的式子已经可以直接做了，只是模数比较恶心…）

或者从组合意义上考虑：

一个点被算进 ，只可能是

  1. 自己对自己的贡献，这个的方案数是

  2. 加入了其他已经分成 份中的一份集合时同集合的点对其的贡献，考虑 个点分成 份的所有划分，每一种划分中当前点都可以加入划分出的 个集合的任意一个，加入的集合中的每一个别的点都对 有 的贡献，当前点一共有 种选取集合的方法，每个集合的点数加起来是

于是有

求第二类斯特林数的一项还是要更简单一些 同样扫一遍即可（同样可用线筛去掉快速幂的 ）

HDU6042 Journey with Knapsack

因为我们最终需要 的 项的系数，上式的后半部分在 次项的系数是拆分数 可以在 算出，但在 次项的系数就是只用 组合的方案不好搞，因此我们尝试把边界扩大到

注意到题目中的特殊条件 所以

所以 。对于一个确定的 一共只有 种 对其有影响，直接暴力算 对卷积到的位置的贡献

然后 只取前 项系数的时候任意两个选了 卷起来都超过范围了

可以得到

然后可以卷积这个的时候处理个前缀和直接线性

总复杂度

BZOJ4772 显而易见的数论

直接求所有分配方案下每个部分大小为定值的有多少个不好求，可以转换一下：

求一个至少有 个 的划分直接就是

搞错了！！！

上面两个式子都不成立！！！

正确的是

然后求 函数

（注意那个 的项来自于 ）

考虑两个互质的数的 之积

令 因为 互质，所以每一对不同的 对应一个唯一的 的

然而在 中可以注意到 和 所以 一定是积性函数可以直接证明了

复杂度经过Wolfram Mathematica 算出来是个 的东西

bzoj 讨论中出题人的写法是枚举 的时候符合要求的 是一堆等差数列，可以预处理出来，这部分复杂度有保证是 的

不知不觉Never Settle

Never Settle