常见数列

贝尔数:n 个数分成若干个非空集合的方案数

  • 递推:

调和级数:,其中是欧拉常数,

自然数幂之和

是关于次多项式。

拉格朗日插值

对于次多项式函数以及个点值,有

因此计算出。那么我们计算,可以代入点值计算,复杂度。事实上预处理一个前缀积和后缀积,其实是阶乘乘上 -1 的幂。这样是可以计算的(有一个预处理的过程)。

斯特林数与自然数幂之和

证明:

:m 个的数互不相同的方案数。

因此得到

伯努利数

定义:

伯努利多项式

伯努利多项式定义为

它的推导过程如下。首先有如下等式:

把右边展开得到

这样我们就得到了

知道这个后,我们考虑伯努利数与自然数幂之和的关系。考虑差分:

因此得到

可以得到

现在问题转化为如何求

,得到

)。

设 EGF

那么得到

容斥原理

ARC 102 E

有 n 个不可取分的 k 面骰子,对于每个,求有多少种方案使得:任意两个骰子朝上的面要么相同,要么和不为。答案对取模。

先枚举。也就是说,……不能同时出现。那么就出现 0 次或者一次。直接枚举有多少组里出现了一个。假设有组。设这个有种选择(左边或者右边)。然后考虑出现了多少次:,其中。然后枚举表示比大的数字出现的次数。把放在一起插版即可。

集训队作业 2018 小 z 的礼物

表示 x 这个礼物第一次得到的时间。要求。考虑容斥。

定下来:直接算随到一个的概率。假设有个 pair 满足,一共有个 pair。那么期望就是

考虑 DP。表示现在考虑第行第个格子,表示每行最后一个元素选不选。考虑是否在子集中。

ARC 96 E Everything on It

题意:求有多少个子集族满足:

  1. 其中任意一个子集都是的子集;
  2. 任意两个子集不同;
  3. 都在其中出现至少两次。

考虑容斥。枚举表示出现次数小于等于。那么答案为

其中表示出现次数小于等于 1 的方案数。

考虑枚举有个集合含有中至少一个,其他集合则不含有

显然不含有的子集族数为

对于这个个集合,我们考虑把分入个集合,有的数字可以不放,每个数字最多出现一次。相当于再拿一个集合出来装垃圾。我们给垃圾堆强制加入数字来保证每个集合非空。同时我们认为所在的集合指向垃圾堆。这样就相当于是个数分成个非空集合,那么方案数就是

至于这个集合的其他数字则可以任意填,并且由于个集合各种含有不同的的数字,因此其他部分就不需要考虑重复的问题了,那么方案数就是

因此得到

ARC 101 E Ribbons on Tree

题意:给你一个 n 个点的数,其中 n 是偶数。问有多少种将个点配成对的方式,使得每对点的路径并覆盖了整棵树。

不合法的情况就是某条边不被经过,相当于这条边被割掉。因此考虑容斥。暴力的做法是枚举被割掉的边集,然后每个连通块内无限制连边的方案数,复杂度

首先考虑无限制连边的方案数。对于一个大小为的连通块,它的配对方案数是

那么考虑 DP 计算容斥贡献。设表示的子树中,所在连通块大小为,被割的边数的奇偶性为的配对方案数。注意,我们只统计被割掉的连通块的配对方案数,所在的连通块暂不统计配对方案数。

假设是根,我们要求的答案显然是

考虑转移,对于的边:

  1. 不割。相当于把所在的连通块接在所在的连通块上。则可以贡献到上。
  2. 割。则贡献到上。

对子树大小取 min,时间复杂度

ARC 93 F

枚举的子集。要求中的所有集合都满足最小值在中,问方案数。记作。答案就是

从大到小考虑 A 中的元素。表示的最小值属于 A。

斯特林反演

下降幂:

通常幂转下降幂:

上升幂:

上升幂转通常幂:

反演公式

斯特林反演:

反转公式

引理:

证明显然。

证明反转公式:

反之亦然。

证明反演公式:

也就是说如果的定义式成立,那么成立。

用另一个反转公式,那么如果的定义式成立,那么成立。这样就证完了。

2018 雅礼集训 方阵

给定的矩阵,每个格子填上中的数字,求任意两行、两列均不同的方案数。

不同:对应位置不同。

考虑只要求行不相同。

表示列的矩阵,行互不相同的方案数。有种可能的行。则

列的答案。枚举中列被分成多少类。

注:

一道例题

给定 n 个结点的树,从某个点出发开始随机游走:在点 u 时,有的概率留在原地,否则等概率向相邻结点移动,直到移动到 1 号点停下。求从每个结点出发直指停下,所花费的时间的 k 次方的期望。

到根结点的期望时间是。我们要求

考虑按照从小到大的顺序做。设

可以按树上高消的套路做了。要记得预处理斯特林数。

另一道例题

设连通块数为 T:。问题转化为求出,它表示选出了个连通块。

表示 n 个点 t 个连通块的图的个数。

问题转化为如何求

那么

容易得到

就是

清华集训 2017 生成树计数

在一个 s 个点的图中,存在 s-n 条边,使图中形成了 n 个连通块,第 i 个连通块中有个点。

现在我们需要再连接 n-1 条边,使得该图变成一棵树。对于一种连边方案,设原图中第个连通块连出了条边,那么这棵树的价值为:

求出所有可能的生成树的价值之和,对取模。

转化为 n 个点的生成树 T:

交换

EGF

带回

定义

那么复合函数求导得到(sum 里是个复合函数)

复杂度

Burnside 引理

ARC 62 F Painting Graphs with AtCoDeer

题意:给出无向图 G,对边染 K 种颜色之一。一个环上面的边旋转后得到的染色方案视为相同,求不同的染色方案数。

求出所有的点双(每个点双是独立的):

  1. 单独的边:方案数为 K。
  2. 单环:
  3. 复合环:可以交换两条边的颜色。只用统计不同颜色出现次数的方案数。插板

乘起来即可。