科普文章 - NOI 一轮复习 IV：组合计数

发表于 分类于
早期作品

NOI 一轮复习 IV：组合计数

知识清单/目录：

  • 加乘原理
  • 二项式系数与容斥原理
  • 概率期望相关
  • 生成函数
  • Burnside 引理
  • 几个特殊数列

注意事项：

  1. 本文旨在复习组合计数中的一些一般思考方向，与代数关系较小，几乎所有内容都是初等的，没有什么数学门槛；
  2. 本文所有计数题答案（无论整数还是其他有理数）默认对 $p=998244353$ 取模。

1. 加乘原理

组合计数的一般形式是：对于给定的集合 $S$，对于其中满足某一性质 $P$ 的元素 $x$ 求和 $f(x)$，即求出：

将 $S$ 称为组合类，$x$ 称为组合对象，$f$ 称为权值函数。

组合类中的对象一般还会定义其大小与各种组合运算，这一点在生成函数部分探讨。

我们有时也直接写成：

一种基本的计数思想是构造双射：

  • 其中一种情况是不同的两个组合类中的组合对象可以一一对应，这样对两个组合类进行计数是等价的。
  • 另一种情况是同一组合类中的组合对象可以建立一一对应（或多个为一组），我们只需抽取每对（或每组）中的一个进行计数，再乘上 $2$（或组大小）即可。

加法原理和乘法原理是计数问题中的最基本工具。

加法原理：

对 $S$ 中的所有元素求和 $f(x)$，等价于将 $S$ 划分为若干个子集 $S_1,\ldots,S_m$ 的不交并，然后对它们分别求和 $f(x)$ 再相加。

乘法原理：

将 $S$ 拆分成 $S_1,\ldots,S_m$ 的笛卡尔积，$S$ 中元素的权值 $f(x)$ 等于其拆分出的各 $S_i$ 元素权值 $f_i(x_i)$ 之积，则对 $S$ 中的所有元素求和 $f(x)$，等价于对每个 $S_i$ 进行 $f_i(x_i)$ 求和后相乘。

乘法原理告诉我们可以交换 $\sum$ 和 $\prod$，而我们也可以交换多个 $\sum$：

这一点常被用于当 $B$ 的权值受 $x$ 制约时的组合计数。

例题 $1$：Rabbit Numbering

求 $n$ 元正整数组 $(x_1,\ldots,x_n)$ 的数量，使得：

  • $x_i\leq a_i$；
  • $x_i$ 两两不等。

令 $S_i=[a_i]=\{1,2,\ldots,a_i\}$，$f(x_1,\ldots,x_n)=[x_1\ne x_2]\ldots[x_1\ne x_n]\ldots[x_{n-1}\ne x_n]$。

则我们要求的就是：

我们尝试分离每一个 $x_i$ 的权值，令：$f(x_1,\ldots,x_{i-1}|x_i)=[x_i\ne x_1]\ldots[x_i\ne x_{i-1}]$，那么要求：

这里就是我们前面提到的”$S_i$ 的权值受 $x_1,\ldots,x_{i-1}$ 制约“的情形，我们尝试将其转化为没有制约的情形，具体地，交换求和号，使得 $a_i\leq a_{i+1}$，那么由于 $x_1,\ldots,x_{i-1}$ 两两不等且不超过 $a_i$，所以 $x_i$ 取与它们都不相等的数，就恰好有 $a_i-(i-1)$ 种方案，这是与 $x_1,\ldots,x_{i-1}$ 无关的，因此根据乘法原理，所求可以写为：

时间复杂度为 $O(n\log n)$。

例题 $2$：[AGC 023 E] Inversions

求 $1,\ldots,n$ 的所有满足 $p_i\leq a_i$ 的排列 $p_{1\ldots n}$ 的逆序对数总和。

首先考虑枚举一对 $(i,j)$，设 $ip_j$ 的方案数。

  1. $a_ip_j$，则 $a_i\ge p_i>p_j$，不妨将 $a_j$ 变为 $a_i$，这样一来 $i,j$ 地位等价，因此 $p_ip_j$ 的情况数相等。
  2. $a_i\ge a_j$，那么不妨算 $p_i<p_j$ 的方案数，再用全体符合条件的排列数去减。

展开式子，可以使用线段树维护，由于时间久远，所以我这里懒得展开了，可以去看原题题解。

时间复杂度为 $O(n\log n)$。

例题 $3$：[THUPC 2021 初赛] 区间矩阵乘法

给定长度为 $n$ 的序列 $a_{1\ldots n}$，有 $m$ 个查询，每次给定 $p_1,p_2,d$，求：

  • $\sum\limits_{i=0}^{d-1}\sum\limits_{j=0}^{d-1}\sum\limits_{k=0}^{d-1}a_{p_1+d\times i+j}a_{p_2+d\times j+k}$。

保证所有下标在 $[1,n]$ 中。

要求的是把 $[p_1,p_1+d^2)$ 和 $[p_2,p_2+d^2)$ 两个下标区间中的数分别排列成 $d\times d$ 矩阵，求两个矩阵乘积的所有位置元素和。

首先解决弱化问题：给定矩阵 $A_{m\times n}$ 和 $B_{n\times r}$，求 $C=A\times B$ 的元素和，可以交换 $\sum$ 得到：

也就是说我们只需要计算 $A$ 每一列的和以及 $B$ 每一行的和即可。

放到原问题上，我们就需要计算 $a$ 序列中一些区间和以及一些下标是公差为 $d$ 等差数列的项的和，由于 $d\leq\sqrt n$，都可以直接维护。

时间复杂度为 $O((m+n)\sqrt n)$。

例题 $4$：

  • 求给定的长度为 $n$ 的序列所有区间异或和的和；
  • 求给定的大小为 $n$ 的集合所有子集异或和的和。

位运算对不同的位有良好的线性性，因此这类问题通常可以分到每一位单独考虑，只需要解决只有 $0,1$ 的问题，代价是额外的一个 $\log v$ 的复杂度。

  • 区间异或和之和：枚举右端点 $r$，再枚举当前算的位，只需求出 $0,\ldots,r-1$ 的前缀异或和中有几个当前位与 $r$ 不同，容易使用一个变量记录。
  • 子集异或和之和：枚举当前算的位，如果存在至少一个 $1$，那么随便取一个 $1$ 出来，将一个子集中的这个 $1$ 的选取状态取反，就会得到异或和等于 $0$ 和 $1$ 的子集的双射，所以为 $1$ 的子集数量是 $2^{n-1}$；否则若没有 $1$，显然所有子集异或和都是 $0$。

时间复杂度为 $O(n\log v)$。

例题 $5$：

给定一棵包含 $n$ 个结点的外向树，求其拓扑排序的个数。

把树当作有根树，一个排列是拓扑序的充要条件是：每个点都是其子树中最早出现的点。

设 $u$ 的子树大小为 $size_u$，那么在所有 $n!$ 个排列中，$u$ 恰好是子树中最早出现的点的概率就应该是 $\dfrac{1}{size_u}$。

同时由于树的优良性质，各个点的限制之间是互相独立的（因为两个点的子树要么是包含关系，要么不交），所以总的方案数其实就是：

时间复杂度为 $O(n)$。

例题 $6$：北大集训 2020 试机题（出自北大集训 2019）

给定 $n$ 个正整数 $d_{1\ldots n}$，求有多少个数列 $a_{1\ldots n}$ 满足：

  • $a_i|d_i$；
  • $\prod\limits_{i=1}^n a_i\leq \prod\limits_{i=1}^n\dfrac{d_i}{a_i}$

我们发现令所有 $a_i$ 都变为 $\dfrac{d_i}{a_i}$ 之后原本的 $\leq$ 就变成了 $\ge$，所以我们建立的条件 $2$ 中 $\leq$ 和 $\ge$ 对应的 $a_{1\ldots n}$ 的一一对应。

因此，我们只需要计数 $\prod\limits_{i=1}^n a_i=\prod\limits_{i=1}^n\dfrac{d_i}{a_i}$ 的方案数 $C$ 和总方案数 $S$，则 $\dfrac{S+C}{2}$ 就是答案。

$S$ 是容易计算的，它就是所有 $d_i$ 因子数之积。

而计算 $C$ 时，由于我们已经将不等号变成了等号，所以对每个素因子是独立的，对素因子指数进行背包即可。

时间复杂度为 $O(n^2\log v)$。

2. 二项式系数与容斥原理

这一段及之后出现大量的 \displaystyle 和普通模式的混用，请勿在意。

定义组合数 $\binom n m$ 或 $C_n^m$ 指的是从 $n$ 个不同物体中挑选 $m$ 个不同物体形成集合的方案，其中 $n\ge m$ 且 $n,m$ 为自然数。

为了得到组合数的计算公式，我们借助排列数这一工具，排列数 $A_n^m$ 表示从 $n$ 个不同物体中挑选 $m$ 个不同物体排成一列的方案。

第 $i$ 步还剩下 $n-i+1$ 个物品，根据乘法原理就可以得到：$A_n^m=n(n-1)(n-2)\ldots(n-m+1)=\dfrac{n!}{(n-m)!}$。

而 $m$ 个物品的一种组合对应了 $m!$ 种排列，因此 $m!\binom n m=A_n^m$，也就是 $\displaystyle\binom n m=\dfrac{n!}{m!(n-m)!}$。

考虑 $(1+x)^n$ 的展开，我们可以看成有 $n$ 个物体，每个物体选就对应最终结果项乘个 $x$，这样选择 $m$ 个不同物体的方案就对应最终结果 的 $m$ 次项系数，因此 $\binom n m$ 就是 $x^m^n$，这个结论被称为二项式定理，因此组合数也称为二项式系数。

当 $n$ 是自然数但 $n<m$ 时，认为 $\binom n m=0$。

二项式系数排列成的一个三角形称为杨辉三角或帕斯卡三角。

二项式系数有很多简单性质：

  • $\displaystyle\binom n 0=1, \binom n 1=n, \binom n 2=\dfrac{n(n-1)}{2}$；
  • $\displaystyle \binom n m=\binom n {n-m}$；
  • $\displaystyle \binom n m=\binom {n-1}{m-1}+\binom {n-1} m$，这是因为从 $n$ 个中选 $m$ 个，枚举最后一个选不选，若选就是从前 $n-1$ 个里选 $m-1$ 个，否则就是从前 $n-1$ 个里选 $m$ 个。
  • $\displaystyle\sum\limits_{i=0}^n\binom n i=2^n$，这是因为根据二项式定理它等于 $(1+1)^n=2^n$；
  • $\displaystyle \sum\limits_{i=0}^n(-1)^{i}\binom n i=0 (n\ge 1)$，这是因为根据二项式定理它等于 $(1-1)^n=0$；
  • $\displaystyle \binom n 1+\binom n 3+\binom n 5+\ldots=\binom n 0+\binom n 2+\binom n 4+\ldots=2^{n-1} (n\ge 1)$，可以由前两个命题得到。

接下来再介绍一下略微不太显然的性质：

  • $\displaystyle (n-m)\times \binom n m=n\times \binom {n-1}m$，直接根据计算公式展开得证。
  • $\displaystyle m\times \binom n m=n\times \binom {n-1}{m-1}$，直接根据计算公式展开得证。
  • $\displaystyle\sum\limits_{i=0}^n i\times \binom n i=n\times 2^{n-1}$，根据上一条可证，据此还可以得到形如 $\displaystyle\sum\limits_{i=0}^n i^k\times \binom n i $ 的计算方法。
  • 上指标求和：$\displaystyle \sum\limits_{i=0}^n \binom i m=\binom {n+1}{m+1}$，组合意义：枚举从 $n+1$ 个物品中选 $m+1$ 个物品中的最后一个物品。
  • 对角线求和：$\displaystyle\sum\limits_{i=0}^n\binom {m+i} i=\binom {m+n+1}{n}$，利用上面第三条简单性质可归纳。
  • 范德蒙德卷积：$\displaystyle \sum\limits_{i=0}^{k}\binom n i\binom m {k-i}=\binom {n+m} k$，组合意义：从大小为 $n,m$ 的两堆中总共选出 $k$ 个物品。
  • 范德蒙德卷积另一形式：$\displaystyle \sum\limits_{i=0}^{\min(n,m-k)}\binom n i\binom m {i+k}=\binom {n+m} {n+k}$，只需将 $\displaystyle \binom n i$ 替换成 $\displaystyle \binom n {n-i}$ 即可。
  • 平方求和：$\displaystyle\sum\limits_{i=0}^n\binom n i^2=\binom {2n} n$，这是范德蒙德卷积第二形式的简单推论。

利用二项式定理解释范德蒙德卷积的本质：$(1+x)^n\times (1+x)^m=(1+x)^{n+m}$。

广义二项式系数

将二项式系数的上指标 $n$ 由自然数扩展到任意实数，就得到了广义二项式系数：$\displaystyle\binom n m=\dfrac{n(n-1)\ldots (n-m+1)}{m!}$，

注意 $m$ 始终必须是一个自然数。

在广义二项式系数的定义下，当 $n<m$ 且 $n$ 是自然数时有 $\binom n m=0$，和我们此前的约定相同。

与之对应的有广义二项式定理：

证明先空着，回去翻一下书。

关于广义二项式系数有一个基本的恒等式：

  • 上指标反转：$\displaystyle \binom n m=\binom {m-n-1}{m}\times (-1)^m$，直接展开即可证明。

多项式系数

还可以从另一个角度对二项式系数进行推广：

将 $n$ 个不同物体划分成 $m$ 个集合，第 $i$ 个集合大小为 $a_i$，有 $\sum a_i=n$，求总方案数，这个问题是多重组合问题。

将方案数记为多项式系数 $\displaystyle \binom n {a_1,a_2,\ldots,a_m}$，则我们可以依次确定每个集合选取哪些元素，也就是：

与之对应的有多项式定理：

通过组合意义证明和二项式定理类似。

组合数的应用

下面介绍几个组合数的实际应用。

首先是十二重计数法中的一部分，将 $n$ 个球放入 $m$ 个盒子中，要求：

  • 球之间互不相同，盒子之间也互不相同：

    • $\text{I}$：无其他限制。

      每个球独立，可以放入 $m$ 个盒子中的任何一个，所以答案为 $n^m$。

    • $\text{II}$：每个盒子至多放一个球。

      首先枚举 $m$ 个盒子中的 $n$ 个放球，然后球之间可以任意交换，所以答案为 $\binom m n\times n!$。

    • $\text{III}$：每个盒子至少放一个球。

      需要使用容斥原理，得到结果为 $\sum\limits_{i=0}^m (-1)^i\times \binom m i\times (m-i)^n$。

  • 球之间互不相同，盒子之间都相同：

    此部分基本需要用到第二类斯特林数。

  • 球之间都相同，盒子之间互不相同：

    • $\text{VII}$：无其他限制。

      最经典的解释方法是隔板法，将 $n$ 个球排成一排，在中间插入 $m-1$ 块隔板，分成 $m$ 段，第 $i$ 段就表示第 $i$ 个盒子里装的球。

      可以看成事先有 $n+m-1$ 个东西，其中要分成 $n$ 个球和 $m-1$ 块隔板。

      所以答案为 $\binom {n+m-1} n$。

    • $\text{VIII}$：每个盒子至多放一个球。

      在 $m$ 个盒子中选 $n$ 个放球，所以答案为 $\binom m n$。

    • $\text{IX}$：每个盒子至少放一个球。

      先给每个盒子塞上一个球，然后转化成 $\text{VII}$。

  • 球之间都相同，盒子之间都相同：

    此部分基本需要用到划分数和生成函数解释。

这里主要要说明的是 $\text{VII}$ 和 $\text{IX}$，归纳出来可以得到：

  • 将 $n$ 划分成 $m$ 个有序自然数的和，方案数等于 $\binom {n+m-1}{n}$；
  • 将 $n$ 划分成 $m$ 个有序正整数的和，方案数等于 $\binom {n-1}{m-1}$。

将 $=$ 改成 $\leq$ 也类似，例如 $\text{VII}$，只需添加一个自然数将少的部分补齐，也就是将 $n$ 划分成 $m+1$ 个有序自然数的和，即可。

另一个和组合数相关的实际问题是路径计数问题：

从网格图的左上角 $(0,0)$ 走到右下角 $(n,m)$，每次只能向右或向下走一步，总方案数为 $\binom {n+m} n$，因为总共要走 $n+m$ 步，其中 $n$ 步是向右的，其余 $m$ 步是向下的。

组合数的求法

  • 情况 $1$：给定 $n$，求所有 $\displaystyle \binom i j$（$0\leq j\leq i\leq n$），模数不一定是素数。

    使用递推式 $\displaystyle \binom n m=\binom {n-1} {m-1}+\binom {n-1} m$ 以及 $\displaystyle\binom n 0=1$，时间复杂度为 $O(n^2)$。

  • 情况 $2$：有 $q$ 组询问，每次给出一组 $a,b$，询问 $\displaystyle\binom a b$（$0\leq b\leq a\leq n$），模数是大于 $n$ 的素数。

    预处理 $n!\bmod p$ 和 $\dfrac{1}{n!}\bmod p$，每次带入公式，时间复杂度为 $O(q+n)$。

    另一种方法是每次暴力计算 $\dfrac{a(a-1)\ldots (a-b+1)}{b!}$，时间复杂度为 $O(\sum b)$，有时会更有用，并且当我们需要递推计算 $\displaystyle \binom n 0,\binom n 1,\ldots,\binom n m$ 时这种方法的复杂度仅为 $O(m)$。

接下来要先说明 Lucas 定理。

Lucas 定理：设 $n,m$ 的 $p$ 进制表示分别是 $\overline{a_k\ldots a_0},\overline{b_k\ldots b_0}$，那么 $\displaystyle\binom n m\equiv \prod\limits_{i=0}^k \binom {a_i}{b_i}\bmod p$，其中 $p$ 是素数，$n,m$ 是自然数。

该定理用二项式定理证明，我们首先需要一个引理：

$(1+x)^{p^k}\equiv (1+x^{p^k})\bmod p$，指两边各项系数对应同余。

这是因为 $\displaystyle\binom {p^k} x\equiv 0\bmod p (x\in [1,p^k-1])$，考察式子上下 $p$ 的幂次即可，这一点稍后详讲。

那么我们来看二项式定理的形式：

我们要求这个式子的 $m$ 次项系数，就需要最右侧连乘式中的指数之和等于 $m$，而由于 $a_i<p$，所以想要用右侧的和组合出 $m$ 的方法至多一种，也就是：

而这正是 Lucas 定理的表述。

这里再写一些和 Lucas 定理关系较大的数论内容。

首先我们看到上面的一个表述：

这是因为 $\displaystyle\binom {p^k} x\equiv 0\bmod p (x\in [1,p^k-1])$，考察式子上下 $p$ 的幂次即可。

事实上，我们可以得到更进一步的表述：

命题：$\displaystyle\binom {n+m} n\equiv 0\bmod p$ 当且仅当 $n$ 与 $m$ 的加法在 $p$ 进制下发生进位，其中 $p$ 是素数。

而这是另一个定理的一个特殊情况：

Kummer 定理：$\dfrac{(n+m)!}{n!\times m!}$ 中质因子 $p$ 的次数恰好为 $n+m$ 计算过程中在 $p$ 进制下的进位次数。

证明：根据简单的数论知识可以知道 $n!$ 中素因子 $p$ 的次数为 $\sum\limits_{i=1}^{+\infty} \lfloor\dfrac{n}{p^i}\rfloor$。

因此这个二项式系数中 $p$ 的幂次就是 $\sum\limits_{i=1}^{+\infty}(\lfloor\dfrac{n+m}{p^i}\rfloor-\lfloor\dfrac{n}{p^i}\rfloor-\lfloor\dfrac{m}{p^i}\rfloor)$。

括号中的这个东西我们称为 $g_i$，根据 $\lfloor\dfrac{a}{b}\rfloor=\dfrac{a-a\bmod b}{b}$，所以有：

令 $n_i=n\bmod p^i, m_i=m\bmod p^i$：

  • 如果 $n_i+m_i<p^i$，那么就对应了 $n+m$ 过程中在第 $i-1$ 位上没有进位到第 $i$ 位，此时根据上面的式子 $g_i=0$；
  • 如果 $n_i+m_i\ge p^i$，那么就对应了第 $i-1$ 位进了一位，此时 $(n+m)\bmod p^i=n_i+m_i-p^i$，所以 $g_i=1$。

综上，$\sum g_i$ 就是 $n+m$ 在 $p$ 进制计算过程中的进位次数，而这也就是 $\displaystyle \binom {n+m} n$ 中 $p$ 这个素因子的出现次数。

下面让我们回到求组合数的问题上。

  • 情况 $3$：有 $q$ 组询问，每次给出一组 $a,b$，询问 $\displaystyle\binom a b$（$0\leq b\leq a\leq n$），模数是较小的（比 $n$ 小的）素数 $p$。

    此时套用情况 $2$ 的做法，不仅复杂度有一个较大的 $n$，同时还会产生 $p$ 的倍数没有逆元的情况。

    因此我们选择用 Lucas 定理转化成 $a,b<p$ 的情形，然后使用情况 $2$ 解决。

    注意此过程的一般实现方法：递归计算 $\displaystyle \binom n m$，如果 $n,m<p$ 则直接计算，否则根据 Lucas 定理有 $\displaystyle \binom n m\equiv \binom {n\bmod p}{m\bmod p}\binom {\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}$，据此进行递归即可，由于 $n\bmod p, m\bmod p<p$，所以其实只会递归一边。

    时间复杂度为 $O(p+\dfrac{q\log n}{\log p})$。

  • 情况 $4$：有 $q$ 组询问，每次给出一组 $a,b$，询问 $\displaystyle\binom a b$（$0\leq b\leq a\leq n$），模数是较小的正整数 $m$，可能是合数。

    这里的处理方法被称为扩展 Lucas，但是实际上和 Lucas 定理关系不大。

    首先设 $m=\prod p_i^{c_i}$，其中 $p_i$ 是素数，也就是说我们将 $m$ 进行了素因数分解，然后我们只需要求出所有 $\displaystyle \binom a b\bmod p_i^{c_i}$ 再用中国剩余定理合并即可。

    而这里求解 $\displaystyle \binom a b\bmod p_i^{c_i}$ 的核心困难是 $\bmod p_i^{c_i}$ 意义下阶乘逆元可能不存在，而解决方法是提取出 $\displaystyle\binom a b$ 中素因子 $p_i$ 的次数，然后对剩余部分用求逆计算。

    设 $a!,b!,(a-b)!$ 中 $p_i$ 的幂次分别为 $u,v,w$，那么就有 $\displaystyle\binom a b= \dfrac{\frac{a!}{p_i^u}}{\frac{b!}{p_i^v}\times \frac{(a-b)!}{p_i^w}}\times p_i^{u-v-w}$，所以接下来我们分别计算形如 $\dfrac{a!}{p_i^u}$ 的式子以及这里的 $u$。

    其中 $u$ 是非常容易计算的，在 Kummer 定理的证明过程中已经写了，它就是 $\sum\limits_{k=1}^{+\infty} \lfloor\dfrac{a}{p_i^k}\rfloor$。

    而形如 $\dfrac{a!}{p_i^u}\bmod p_i^{c_i}$ 的式子可以采用递归的方法计算：

    在 $\bmod p_i^{c_i}$ 意义下，后者是一个以 $p_i^{c_i}$ 为周期的函数的前缀积，通过一定的预处理（$O(p_i^{c_i})$）可以在 $O(1)$ 的时间内求出。

    而前面的阶乘则要继续递归。

    上面过程做一遍的复杂度是 $O(p_i^{c_i}+\dfrac{\log n}{\log p_i})$，所以算上 $q$ 次询问的时间复杂度不超过 $O(m+q\omega(m)\log n)$。

除了直接求一个组合数的值以外，还有一些相关的问题，这里也提一下：

  • 组合数比大小：

    给定两个二项式系数 $\displaystyle \binom a b$ 和 $\displaystyle \binom c d$，比较它们的大小。

    将两边取对数，有 $\ln \displaystyle \binom a b=\sum\limits_{i=1}^a \ln i-\sum\limits_{i=1}^b\ln i-\sum\limits_{i=1}^{a-b}\ln i$，而这个数是不超过 $a\ln a$ 的，直接比较两个对数的大小即可。

  • 组合数前缀和：

    有 $q$ 组询问，每组询问给定 $n,m$，求出 $\displaystyle\sum\limits_{i=0}^m \binom n i$。

    这里所说的是一种 $O((q+n)\sqrt n)$ 的做法，设题目所求为 $S(n,m)$。

    根据定义有 $\displaystyle S(n,m+1)=S(n,m)+\binom n {m+1}$，而 $\displaystyle S(n,m-1)=S(n,m)-\binom n {m-1}$。

    此外根据杨辉三角的递推公式，我们有 $\displaystyle S(n+1,m)=2\times S(n,m)-\binom n m$，反过来就是 $\displaystyle S(n-1,m)=\dfrac{S(n,m)+\binom{n-1}{m}}{2}$。

    所以可以套上莫队进行求解，事实上只需要有 $S(n,m)$ 到 $S(n,m+1)$ 和 $S(n+1,m)$ 就符合使用莫队的条件了，时间复杂度为 $O((q+n)\sqrt n)$。

相关题目

为了保证前面内容的连贯性，将例题全都放到这里。

例题 $7$：[ABC 154 F] Many Many Paths

求 $\displaystyle \sum\limits_{i=a}^b\sum\limits_{j=c}^d \binom {i+j}{i}$。

固定 $j$ 后是一个对角线求和，根据公式，答案等于：

然后这是两个上指标求和，我们知道答案为：

当然，上指标求和与对角线求和的本质是相同的。

时间复杂度为 $O(a+b+c+d)$。

例题 $8$：[CERC 2015] Frightful Formula

给定 $F(1,i)$ 和 $F(i,1) (i\in [1,n])$，并且有 $F(i,j)=aF(i-1,j)+bF(i,j-1)+c (i,j\in [2,n])$，求 $F(n,n)$。

解一：

考虑按照网格图路径计数的方法，给递归式赋予一个合适的意义。

由于有形如 $aF(i-1,j)+bF(i,j-1)$ 这样的式子，我们如下定义这一部分答案：从 $(2,i)$ 或 $(i,2)$ 往 $(n,n)$ 每次向右或向下行走，向右的权值为 $b$，向下的权值为 $a$，路径权值为每一步权值的积，将所有路径权值之和乘上 $F(1,i)$ 或 $F(i,1)$ 后求和。

类似地，我们对 $c$ 也赋予一个意义：从每个 $(i,j) (i,j\in [2,n])$ 出发，到 $(n,n)$ 且每次只能向右或向下行走，向右权值为 $b$，向下权值为 $a$，求所有路径权值之和乘上 $c$。

根据路径计数的结论，答案如下：

前两项直接暴力计算即可，我们考虑最后一项，将之稍加改写：

这似乎是上题的加强版，有趣的是，我的解法在解决本题是当 $a=b=1$ 时需要特判并使用上题的解法解决，因此这种解法并不能包含掉上题。

考虑设 $\displaystyle S_i=\sum\limits_{j=0}^{n-2}\binom {i+j} j\times b^j$，答案为 $\displaystyle\sum\limits_{i=0}^{n-2} S_i\times a^i$，我们只需要想办法计算 $S_i$。

可以建立 $S_i$ 和 $S_{i+1}$ 之间的递推关系：

可以解得：

当 $b\ne 1$ 或 $a\ne 1$ 时我们可以采用这个递推，否则采用上题的做法。

这是我在做集训队作业的时候的原解法。

解二：

由于 $c=0$ 的情况是容易的，所以我们可以将问题转化为 $c=0$ 的情况。

考虑令 $G(i,j)=F(i,j)-\Delta$，使得 $G(i,j)=aG(i-1,j)+bG(i,j-1)$，那么有 $\Delta=a\Delta+b\Delta+c$，所以令 $\Delta=\dfrac{c}{1-a-b}$ 即可。

问题到这里已经基本解决，但这道原题的模数是较小的 $10^6+3$，有可能出现 $1-a-b\equiv 0$ 的情况，所以我们还需要对 $a+b\equiv 1$ 的情况进行讨论。

考虑改进 $\Delta$ 的定义，将它设为函数 $\Delta(i,j)$，我们依然有 $\Delta(i,j)=a\Delta(i-1,j)+b\Delta(i,j-1)+c$，我们可以设 $\Delta(i,j)=c(i+j)$，可以验证当 $a+b\equiv 1$ 时符合条件。

两种做法复杂度都为 $O(n)$，但解一相对基础，解二似乎需要一定的构造和观察。

例题 $9$：[AHOI 2017 / HNOI 2017] 抛硬币

甲抛掷 $a$ 次硬币，乙抛掷 $b$ 次硬币，问甲抛出正面朝上的次数更多的方案数，模数为 $10^9$，保证 $a\ge b$。

$a,b$ 可达 $10^{15}$，而 $a-b\leq 10^4$。

将甲抛出的正面朝上更多的情况称为甲胜，一样多的情况称为平局，否则称为乙胜。

不妨从 $a=b$ 的情况开始讨论，这有些类似例题 $6$，我们知道甲胜和乙胜的情况一一对应，因此只需要算出总方案数 $S$ 和平局数 $C$，那么 $\dfrac{S-C}{2}$ 就是答案。

显然 $S=2^{2a}$，而平局的情况，我们只需枚举有几次硬币朝上，所以答案就是：

接下来我们尝试用相同的方法讨论 $a>b$ 的情况。

先前是甲胜和乙胜一一对应，但是现在由于甲抛的次数多，所以不管是乙胜还是平局，将每次抛硬币结果反转后都会得到一个甲胜的局面，仔细思考发现这其实也是一个双射：乙胜的情况和平局的情况加起来和一部分甲胜的情况一一对应。

因此我们只需要计算那些本来是甲胜，全部反转后还是甲胜的方案数 $C$，则 $\dfrac{S+C}{2}$ 就是答案。

设这种局面中甲正面朝上 $i$ 次，乙正面朝上 $j$ 次，列出 $i>j, a-i>b-j$ 的不等式，得到 $1\leq i-j\leq a-b-1$。

由此可以直接写出答案：

注意式子中的 $u,v$ 分别是 $j$ 和 $i-j$。

交换求和顺序，里面可以使用范德蒙德卷积的第二形式化简：

于是我们只需要使用扩展 Lucas 计算 $O(a-b)$ 次组合数即可得到结果。

需要特别注意的是，$a=b$ 的情况由于平局不对应甲胜，所以和后面的式子不同！

时间复杂度为 $O((a-b)\log a+5^9)$。

例题 $10$：

求有多少组 $a_1,\ldots,a_k$ 满足：

  • $a_i\leq x_i$；
  • $\displaystyle\binom {\sum a_i}{a_1,\ldots,a_k}$ 是奇数。

我们可以通过将多项式系数拆为二项式系数的乘积，从而推广 Kummer 定理：

倒序合并可以知道，这个数不是 $p$ 的倍数，当且仅当 $a_1+\ldots+a_k$ 的任何一步中都没有进位。

此处 $p=2$，这个条件可以等价地刻画为：所有 $a_i$ 的二进制表示两两无交。

随后我们可以数位 DP，令 $f(i,S)$ 表示已经考虑二进制下最高 $i$ 位，目前 $S$ 集合中的所有 $a_i$ 的高位是和 $x_i$ 相等的，通过枚举第 $i$ 位属于哪个数（或都不属于）转移。

时间复杂度为 $O(2^k\times k\log x_i)$。

容斥原理

给定 $n$ 个集合 $S_1,\ldots,S_n$，如果我们可以轻松地算出它们中一些的交集大小，则可以据此计算它们的并集大小：

其中 $[n]$ 指 $\{1,2,\ldots,n\}$，这个式子的含义是，这些集合并集的大小可以通过枚举一个子集的集合，将它们求交并乘上 $-1$ 的子集大小次方求和得到。

这个式子的一种理解是通过二项式定理：

因此并集中的每个元素都被计算了恰好一次。

这个式子就是容斥原理的基本表达，此外它还有一个常见形式：

其中当 $T=\varnothing$ 时后面的式子定义为全集大小，容易发现这个式子只是前面那种形式取补得到的，但这种形式通常更有用。

我们可以直观地理解容斥原理：

  • $n$ 件事至少发生一件的方案数，可以通过其中每个子集同时发生的方案计算；
  • $n$ 件事都不发生的方案数，可以通过其中每个子集同时发生的方案计算。

例题 $11$：伯努利信封问题

求 $1,\ldots,n$ 的排列 $p_1,\ldots,p_n$ 的数量，使得 $i\ne p_i$。

通常称错排问题。

设 $S_i$ 为所有满足 $i=p_i$ 的排列构成的集合，我们要求的就是 $|\overline{\bigcup\limits_{i=1}^n S_i}|$，采用容斥原理，求若干个 $S_i$ 交的大小，而这等价于若干个 $p_i=i$，剩下的数自由排列，这只和子集大小有关，因此我们可以写出答案：

将里面打开，可以得到如下结果：

设此结果为 $a_n$，我们还可以据此得到 $a_n$ 的递推式：

并且有 $a_1=0$，随后我们可以将一个 $a_{n-1}$ 改写成 $a_{n-2}\times (n-1)+(-1)^{n-1}$，所以：

这个问题还有多种做法，如考虑 $n$ 在排列中的位置，或直接使用生成函数解决。

时间复杂度为 $O(n)$。

例题 $12$：

求正整数列 $a_{1,\ldots ,n}$ 的数量，满足：

  • $a_i\leq x_i$；
  • $\sum a_i=S$。

设 $S_i$ 是满足 $a_i>x_i$ 且 $\sum a_i=S$ 的数列集合，我们要求 $|\overline{\bigcup\limits_{i=1}^n S_i}|$，采用容斥原理，求一些 $S_i$ 的交，我们不妨先将这些 $S_i$ 对应的 $x_i$ 取满，然后就没有额外的限制了，可以采用隔板法，所以：

套用容斥原理的式子，时间复杂度为 $O(2^n)$。

例题 $13$：脑力

给定 $n$ 个字符串 $T_1,\ldots,T_n$，字符串中有些问号表示可以填上任意小写字母，问所有填写方案中这些串构成的字典树结点数之和。

设 $S_i$ 是字典树上第 $i$ 个串的所有前缀对应结点构成的集合，我们要求 $|\bigcup\limits_{i=1}^n S_i|$，用容斥原理转化成求每个子集的 $S_i$ 的交。

而 $S_i$ 的交就是它们对应的串的 LCP，可以通过枚举 LCP 长度算方案数求出。

时间复杂度为 $O(2^n\times |T_i|)$。

例题 $14$：[COCI 2009-2010 #6] XOR 加强版

给定 $n$ 个顶点形如 $(x_i,y_i),(x_i,y_i+l_i),(x_i+l_i,y_i)$ 的等腰直角三角形，求它们的异或面积并。

原题 $n\leq 10$，这里考虑 $n\leq 500$。

这是一个变形的容斥原理，我们可以知道答案一定可以写成每个子集的交乘上一个系数求和。

事实上稍加推导可以发现，大小为 $m$ 的子集的容斥系数为 $(-2)^{m-1}$，提供一个归纳性证明：

我们可以考虑枚举一个三角形 $Tri$，求交集为 $Tri$ 的子集的容斥系数和。

而这可以再套一层三维差分的容斥，转化为计算八个形如“包含 $Tri$ 的所有三角形集合的所有子集的容斥系数和”的东西。

这一点是容易的，设包含 $Tri$ 的三角形有 $m$ 个，则系数和为：

也即当 $m$ 为偶数时系数为 $0$，否则系数为 $1$。

枚举三角形的三条边并通过三维差分计算即可，时间复杂度 $O(n^3)$。

例题 $15$：[AGC 005 D] ~K Perm Counting

求 $1,\ldots,n$ 的排列 $p_1,\ldots,p_n$ 的数量，使得 $|i-p_i|\ne k$。

$O(n^2)$。

容斥，考虑钦定 $u$ 个满足 $|i-p_i|=k$ 的方案数。

我们建立一张二分图，左边的点 $i$ 连到右边的点 $i+k$ 和 $i-k$，那么这个方案数就是我们要钦定在这张图上选择 $u$ 条边构成匹配。

可以发现这个二分图是 $2k$ 条链（或不足），假设一条链包含 $b$ 条边，要选择 $a$ 条互不相邻的边，枚举最后一条边选不选，然后将前面选的边和其下面一条一定不能选的边打包，可以得到方案数为：

而我们有 $2k$ 条链，只需做个背包，将它们整合到一起即可。

时间复杂度为 $O(n^2)$。

例题 $16$：[ARC 101 C] Ribbons on Tree

将给定的包含偶数 $n$ 个点的树上的点两两配对，使得每对点之间路径的并集包含了每一条树边，求方案数。

容斥，考虑枚举一个边集 $E$ 求 $E$ 中所有边没有被任何路径经过的方案数。

删除 $E$ 中的边后树分成 $|E|+1$ 个连通块，显然 $E$ 中的边都不被经过等价于任何一对点都在同一连通块中。

那么每个连通块独立，设一个连通块大小为 $m$，随意钦定一个顺序，让每个没被之前选过的点选择一个其他点结队，方案数显然是 $(n-1)!!$。

接下来树形 DP，用 $f(i,j)$ 表示 $i$ 子树中 $i$ 所在连通块大小为 $j$ 时的容斥系数之和，这是一个简单的树形背包，注意 $f(i,0)$ 表示 $i$ 到父亲的边不被覆盖的方案，需要特殊计算。

时间复杂度为 $O(n^2)$。

二项式反演

上面介绍的容斥原理只能用来求一些集合的并的大小，我们可以将这个东西特殊化以后进行一下扩展：

问题：有 $n$ 个集合 $S_1,\ldots,S_n$，我们要求其中属于恰好某指定 $k$ 个集合的元素数量，并且任选 $k$ 个集合算出来的答案是一样的。

不难发现，错排问题等只是该问题当 $k=0$ 时的特例。

我们设问题的答案为 $g_k$，考虑先求出一个 $f_k$，表示至少属于某指定 $k$ 个集合的元素数量，那么枚举实际上属于几个集合，有：

现在我们使用容斥来推出 $g_k$，考虑使用 $f_i$ 容斥，通过枚举指定 $k$ 个集合构成的集合 $S$ 的超集：

整理一下就是：

通过 $f_k$ 的表达式推出 $g_k$ 关于 $f_i$ 的表达式，上面这个过程就是二项式反演。

二项式反演还有另一形式：

这个式子中，$f_k$ 的实际意义是至多属于某指定 $k$ 个集合的元素数量。

也就是说，二项式反演能够帮我们完成至少到恰好，或者至多到恰好的转化。

然而上面所展示的并非二项式反演最令人惊叹的部分，事实上我们有：

这个式子非常对称，并且想要证明是很容易的：令 $g’_k=g_k\times (-1)^k$，就变成了上面的形式。

而关于它的本质我想等到继续学了线性算法和其他反演理论之后再回来写。

例题 $17$：[Luogu P6596] How Many of Them

求 $n$ 个点的带标号无向连通图中有多少个的割边数不大于 $m$。

这里我们需要求“至多”，而钦定“至少”是容易的，所以我们将“至多”转化为“恰好”，再将“恰好”转化为“至少”。

考虑求出至少 $m$ 条割边的方案数，这里需要一点生成函数的知识，首先 $m$ 条割边把图分成 $m+1$ 个部分，假设大小分别为 $a_1,\ldots,a_{m+1}$，那么通过割边将它们连接的方案数为 $n^{m-1}\times \prod\limits_{i=1}^{m+1}a_i$，而本题中点有标号，故采用 EGF 进行计算，具体地，一个部分的 EGF 设为：

则我们要求的至少 $k$ 条边的方案是：

随后使用二项式反演导出至多 $k$ 条边的方案。

事实上，可以使用 NTT 将时间复杂度优化到至少 $O(n^2\log n)$。

例题 $18$：[NOI Online #2 提高组] 游戏

一棵 $2m$ 个点的有根树上有 $m$ 个黑点和 $m$ 个白点，对于每个 $k$ 求将黑点和白点两两匹配的方案数，使得恰有 $k$ 对点为祖先关系。

通过二项式反演将“恰好”转化为“至少”，即计算钦定 $k$ 对祖先关系的方案数 $f_k$。

这可以通过一个树形 DP 求出，令 $f(u,k)$ 表示 $u$ 的子树中钦定 $k$ 对祖先匹配的方案数，这样设计状态是足够的，因为根据 $k$ 以及 $u$ 子树内的黑白点数量，可以知道剩余的黑白点数量，转移即树形背包，并在子树根结点处处理根和子树中点的匹配。

时间复杂度为 $O(m^2)$。

例题 $19$：[CF 1228 E] Another Filling the Grid

给 $n\times n$ 矩形中每个格子填上一个 $[1,k]$ 中的整数，使得每行每列的最小值都为 $1$。

这有些像错排问题，但是情况是二维的，本质也是一个 $k=0$ 的二项式反演。

容斥，考虑钦定有 $a$ 行和 $b$ 列的最小值不是 $1$，那么方案数就是：

再设恰有 $a$ 行 $b$ 列的最小值不是 $1$ 的方案数为 $g(a,b)$，我们要求 $g(0,0)$，先列出 $f,g$ 的关系：

这里我们需要借助二维的二项式反演，我们可以将两个求和分步反演，令 $h(a,b)$ 表示钦定 $a$ 行，并恰好 $b$ 列的最小值不是 $1$，则 $h$ 和 $f$ 之间是关于列一维的二项式反演，而 $h$ 和 $g$ 之间是关于行一维的二项式反演：

综合起来就有：

而 $g(0,0)$ 就是我们所要求的。

时间复杂度为 $O(n^2)$。

题目中这种二项式反演的扩展情形在更高维也是成立的，因为 $\sum$ 可以分步反演。

莫比乌斯反演

这里只介绍一些莫比乌斯反演的基本内容，其他数论求和内容不在这里写。

一般反演的套路就是在前缀和与差分之间转化，例如自然的前缀和与差分之间就是反演，二项式反演可以看作一种“二项前缀和”和“二项差分”的转化，而莫比乌斯反演是 Dirichlet 前缀和与 Dirichlet 差分的转化。

设有数论函数 $g_i$ 和 $f_i$，如果满足：

那么称 $f$ 是 $g$ 的 Dirichlet 前缀和，$g$ 是 $f$ 的 Dirichlet 差分。

我们可以找到很多数论中这种运算与多项式乘法之间的关系，例如 Dirichlet 前缀和实际上就是将一个函数 $g$ 与 $1$ 函数 $1(n)=1$ 进行 Dirichlet 卷积（其实就是高维多项式卷积）的结果，一如前缀和可以看成一个函数与 $\dfrac{1}{1-x}$ 的卷积，事实上 Dirichlet 前缀和就是高维前缀和。

设 $k$ 有 $c$ 个素因子 $p_1,\ldots,p_c$，回忆 $c$ 维函数 $F(a_1,\ldots,a_c)$ 的前缀和，其差分为：

将它套到数论背景上，我们定义莫比乌斯函数 $\mu(k)$：如果 $k$ 是一个 Square-Free Number（没有平方因子），那么若 $k$ 有奇数个素因子则 $\mu(k)=-1$，否则 $\mu(k)=1$；如果 $k$ 有平方因子，那么 $\mu(k)=0$。

于是，我们会看到：

这就是莫比乌斯反演，这和上面的高维差分是等价的，这告诉我们数论函数的 Dirichlet 差分由它与莫比乌斯函数卷积得到。

类似二项式反演，对于后缀和也有类似的莫比乌斯反演形式：

通过埃氏筛法，我们可以在 $O(n\log\log n)$ 的时间内计算 Dirichlet 前缀和与 Dirichlet 差分，但这与本文无关。

相关理论后续会用 Bell 级数进一步说明。

例：求证 $\varphi=\mu id, id=\varphi 1$，其中 $*$ 是 Dirichlet 卷积，$id(n)=n$。

证明：

设全集 $U=[n]$，用容斥原理计算 $\varphi(n)$。

设 $n=\prod\limits_{i=1}^m p_i^{c_i}$，再设 $S_i$ 表示满足 $p_i|k$ 的不超过 $n$ 的正整数 $k$ 的集合，我们要求 $|\overline{\bigcup\limits_{i=1}^n S_i}|$。

若干个 $S_i$ 的交就等于 $n$ 除以它们对应 $p_i$ 的乘积，而大小为 $c$ 的子集容斥系数为 $(-1)^c$，正好等于这些 $p_i$ 乘积的莫比乌斯函数，所以：

也就是 $\varphi=\muid$ 了，也就是说欧拉函数是恒等函数的 Dirichlet 差分，那么 $id$ 就是 $\varphi$ 的 Dirichlet 前缀和，也即 $id=\varphi1$。

例：求证 $\mu *1=\varepsilon$，其中 $\varepsilon(n)=[n=1]$。

不难发现 $\varepsilon(n)$ 是数论函数关于 Dirichlet 卷积的单位元，而所谓 $\mu*1$ 可以理解成先将单位元差分，再前缀和，当然保持不变。

这个式子是大多数数论函数求和题的核心式子，我们通常通过这个式子将 $\gcd(a,b)=d$ 转化成 $d|gcd(a,b)$。

Min-Max 容斥

Min-Max 容斥是一种将集合最大值用其子集最小值表示的方法，当然由于相对全体实数来说，Min 和 Max 这两种运算是对称的，所以反过来也成立。

设有数集 $S$，令 $\max(S),\min(S)$ 分别表示其中最大值和最小值，那么有：

对此我们可以用普通的容斥原理来解释当 $S$ 为正整数集的情形：设 $S=\{S_1,\ldots,S_m\}$，令 $T_i$ 表示不大于 $S_i$ 的正整数集合，则 $\max(S)=|\bigcup T_i|$，而 $\min(S)=|\bigcap T_i|$，上面的式子显然就是容斥原理换了个皮。

对于一般情况，有一种容易理解的解释：考虑 $x\in S$，设有 $t(x)$ 个数比它大，那么在右边就计算了 $\displaystyle\sum\limits_{i=0}^{t(x)}(-1)^i\binom {t(x)} i=[t(x)=0]$ 次，所以只有最大值被保留下来。

由于 $\max(S)=-\min(-S)$（$-S$ 是 $S$ 中所有数取相反数得到的集合），所以也有：

到这里，观察普通的容斥和 Min-Max 容斥，我们已经注意到了：

  • 针对集合的普通容斥中，包含是定义在集合上的偏序关系，而交并分别是取下界和上界；
  • 针对实数的 Min-Max 容斥中，不大于是定义在实数集合上的偏序关系，而 $\min,\max$ 分别是取下界和上界。

所以也许我们能将这样的式子推广到其他偏序上去，例如：

由整数的整除偏序可以导出 GCD-LCM 容斥：

当然这里举的例子并没有什么用，因为这本质上只是高维的 Min-Max 容斥。

上面这段可以当成我的胡说八道，实际上只有一个偏序集的任何一个子集有上下确界并且能定义加减运算时才有可能成立。

接下来考虑更进一步，如何用子集的 $\min$ 表示一个集合的第 $k$ 大数，先给出结论：

证明同样考虑贡献，由于 $|T|\ge k$，所以比第 $k$ 大数更大的数一定不会在右边出现。

然后，考虑第 $l>k$ 大的数的贡献，它是：

这个等式之前二项式系数漏写了，通过组合意义证明：从 $l-1$ 个里面选 $i-1$ 个，再从这 $i-1$ 个里选 $k-1$ 个，等价于先直接选 $k-1$ 个，再从没选的 $l-k$ 个里补出来 $i-k$ 个。

后面这个我们就比较熟悉了，它和基本的 Min-Max 容斥一样，只有 $l=k$ 时才为 $1$，因此上面的式子成立。

当然，式子中的 $\min$ 和 $\max$ 互换也是正确的。

Min-Max 容斥的一个常见用途也是将“完全”转化为“至少”，假设有 $n$ 个事件，我们需要计算它们全部发生的期望时间，可以转化为计算某个子集至少发生一件的期望时间。

例题 $20$：[Luogu P4707] 重返现世

有 $n$ 种原料，每秒随机生成一种，生成第 $i$ 种的概率为 $\dfrac{p_i}{m} (m=\sum p_i)$，问第一次集齐 $k$ 种原料的期望时间。

$O(n(n-k)m)$。

设第 $i$ 种原料在时间 $t_i$ 第一次被收集到，我们要求 $t_i$ 中的第 $q=n-k+1$ 大数的期望。

套用 Min-Max 容斥，我们得到：

而 $\min(T)$ 表示第一次收集到 $T$ 中原料的期望时间，也就是说之前只有其他的原料，所以有：

那么我们可以设计一个背包，令 $dp(i,j,k)$ 表示前 $i$ 个原料中大小为 $j$，且其 $\sum p=k$ 时的集合数量，转移显然：

时间复杂度是 $O(n^2m)$ 的。

下面就需要优化了，一般这种 DP 的优化思路就是将一部分系数通过组合意义或组合恒等式化到 DP 值中去，这里我们就进行这样的尝试，设：

也就是说，前 $i$ 个原料的所有 $\sum p=j$ 的子集的后面这个式子的和，我们将 $|T|$ 计入 DP 值，从而将一个大小为 $n$ 的维度替换成了大小仅为 $q=n-k+1$ 的维度。

转移时，考虑到 $(-1)^{|T|-k}\displaystyle \binom {|T|-1}{k-1}=(-1)^{|T|-1-k+1}\binom {|T|-2}{k-1}+(-1)^{|T|-2-k}\binom {|T|-2}{k-2}$，所以有：

时间复杂度为 $O(n(n-k)m)$。

例题 $22$：[HAOI 2015] 按位或

有一个初始为 $0$ 的数 $x$，每秒按照数 $i$ 权重 $p_i$ 来随机选择一个 $[0,2^n-1]$ 中的数，然后将 $x$ 或上这个数，求第一次 $x$ 变为 $2^n-1$ 的期望时间。

设 $t_i$ 表示第 $i$ 个二进制位第一次在 $x$ 中为 $1$ 的期望时间，我们要求 $\max(t_i)$ 的期望，根据 Min-Max 容斥只要对子集 $T$ 计算 $\min(T)$ 的期望。

和上题类似，每次只能选择不在 $T$ 中的位，所以有：

只需要计算一个子集和即可，使用 FWT 即可算出。

时间复杂度为 $O(n\times 2^n)$。

例题 $21$：[PKUWC 2018] 猎人杀

按如下规则构造 $1,\ldots,n$ 的排列：每次从未被选择的元素中以第 $i$ 个元素 $p_i$ 的权重随机选择一个，求 $1$ 是最后一个的概率。

好吧，我的理解里这题和 Min-Max 容斥有点不大像，但还是放这里写一下。

考虑容斥，枚举排在 $1$ 后面的数的集合 $S$，此时可以忽略其他数，$1$ 排在 $\{1\}\cup S$ 中的第一个，这个概率显然是 $\dfrac{p_1}{p_1+\sum\limits_{j\in S}p_j}$。

然后我们可以背包一下，算出不包含 $1$ 的子集中所有 $\sum p_j=x$ 的容斥系数之和 $f(x)$，做个背包即可实现。

时间复杂度为 $O(n\times \sum p_i)$，如果要继续优化可以使用分治 NTT。

4. 生成函数

不写 FFT。

从形式幂级数谈起

对于数列 $f_i (i\in \mathbb{N})$，定义其形式幂级数 $F(x)$ 为：

与一般意义上的多项式不同，形式幂级数允许无限项的求和，而在数学推导后对各种操作进行实现时，我们通常只能取其前 $n$ 项进行计算，此时应表示成：

以表示 $F(x)$ 的 $0$ 到 $n-1$ 次项组成的多项式。

$F(x)$ 只是 $f_i$ 的一种表现形式，在进行各种运算时，我们均假定 $F(x)$ 收敛。

定义形式幂级数的几个基本运算如下（多项式运算的扩展），设 $A(x)=\sum\limits_{i=0}^{+\infty}a_ix^i, B(x)=\sum\limits_{i=0}^{+\infty}b_ix^i$：

  1. 两形式幂级数相等：

    即两个幂级数每一项的系数都相等。

  2. 两形式幂级数相加减：

    容易发现，形式幂级数加法具有交换律和结合律，且 $0$ 为加法单位元。

  3. 两形式幂级数相乘（卷积）：

    和多项式乘法的定义基本相同，只是拓展到了无限项。

    容易发现，形式幂级数卷积具有交换律，结合律以及对加法的分配率，且 $1$ 为乘法单位元，如果两个形式幂级数 $A(x),B(x)$ 的乘积在 $\bmod x^n$ 意义下为 $1$，则称它们在 $\bmod x^n$ 的意义下互为乘法逆元。

  4. 形式幂级数求导：

    导函数 $A’(x_0)$ 也写为 $\dfrac{\mathrm{d}A}{\mathrm{d}x}(x_0)$，高阶导数写作 $A^{(k)}(x)$，即 $A^{(k)}(x)=(A^{(k-1)})’(x)$。

    加法运算：$(A+B)’=A’+B’$；

    乘法运算：$(AB)’=A’B+AB’$；

    复合运算：$\dfrac{\mathrm{d}B}{\mathrm{d}x}=\dfrac{\mathrm{d}B}{\mathrm{d}A}\times \dfrac{\mathrm{d}A}{\mathrm{d}x}$，即若 $C(x)=B(A(x))$，则 $C’(x)=B’(A(x))A’(x)$。

  5. 形式幂级数积分：

    此为不定积分，定积分类似，设 $B(x)=\displaystyle\int A(x)\mathrm{d}x$，则 $\displaystyle\int_{x_1}^{x_2} A(x)\mathrm{d}x=B(x_2)-B(x_1)$。

    所以，如果要去除最后的常数 $C$，应该计算 $\displaystyle\int_0^{x_0}A(x)\mathrm{d}x$。

    求导和积分互为逆运算，但是注意求导后积分可能会失去常数项信息。

考虑在 $\bmod x^n$ 的意义下实现以上运算，加减法以及导数积分都是可以轻松做到 $O(n)$ 的，而计算卷积时可以利用 FFT，做到 $O(n\log n)$ 的复杂度。

泰勒展开和牛顿迭代

没学过数分，一堆东西不会证明。

对于一个解析式和图像可能比较奇怪或难以处理的函数 $G(x)$，我们选取一点 $x_0$，采用一个形式幂级数 $F(x)$ 来在 $x_0$ 的某一邻域内拟合 $G(x)$ 的图像，这个过程就叫做泰勒展开。

更具体地说，对于曲线 $G(x)$，如果它在 $x=x_0$ 处具有 $n$ 阶导数，那么可以用关于 $x-x_0$ 的 $n$ 次多项式 $F(x)$ 来在 $x_0$ 的某一邻域内逼近 $G(x)$ 的值，泰勒公式保证了 $G(x)-F(x)$ 是 $(x-x_0)^n$ 的高阶无穷小。

我们先从较简单的形式开始，先令 $x_0=0$。

考虑形式幂级数 $F(x)$ 的各阶导数，我们希望对于任意 $i\in [0,n]$ 中的整数，都有 $F^{(i)}(0)=G^{(i)}(0)$。

先考虑 $n$ 阶导数（设 $a_i$ 为 $F(x)$ 的各项系数）：

所以我们可以得到：

类似地，再考虑 $n-1$ 阶导数：

所以我们可以得到：

以此类推，我们可以得到，对于每一个 $i\in [0,n]\cap \mathbb{Z}$，都有 $a_i=\dfrac{G^{(i)}(0)}{i!}$，所以：

当 $n\to +\infty$ 时，即：

这个式子是泰勒展开 $x_0=0$ 的特殊情形，称为麦克劳林公式。

当 $x_0\ne 0$ 时，我们只需将新的 $F(x)$ 设为原来的 $F(x-x_0)$ 即可，因为我们只需要保证求 $i$ 次导时只有 $i$ 次项系数会影响结果，那么将原来的 $x$ 换成 $(x-x_0)$ 后恰有 $F(x)$ 中每个 $(x-x_0)^i (i>0)$ 都是 $0$，所以：

当 $n$ 趋于无穷时，我们就可以认为在 $x_0$ 的某一邻域内，$G(x)=F(x)$，但是形式幂级数的研究基于 $F(x)$ 收敛的假设，所以我们不考虑 $G(x)-F(x)$ 是否发散，当成收敛来处理。

  1. 指数函数 $G(x)=e^x$。

    由于 $(e^x)’=e^x$，所以 $G^{(i)}(x)=G(x)=e^x$，取 $x_0=0$，则 $G^{(i)}(x)=1$，因此：

    当我们取 $x=1$ 时，即可以得到一个非常常见的关于 $e$ 的等式：$e=\sum\limits_{i=0}^{+\infty} \dfrac{1}{i!}$。

  2. 对数函数 $G(x)=\ln (x)$。

    由于 $(\ln (x))’=\dfrac{1}{x}$，接下来再根据 $x^{\mu}$ 的求导法则即可得到 $G^{(i)}(x)=(-1)^{i-1}\times (i-1)!\times x^{-i}$，其中的 $(i-1)!$ 可以与泰勒展开中的 $i!$ 抵消，只剩下了 $\dfrac{1}{i}$。

    我们取 $x_0=1$ 进行展开（因为 $\ln (x)$ 在 $x=0$ 处不存在导数）：

    稍作变换即可得到一个我们更为熟悉的式子：

  3. 正弦/余弦函数 $G(x)=\sin (x)$ 及 $G(x)=\cos (x)$。

    对正弦或余弦函数求导，我们可以得到一个循环：$\sin\to \cos\to -\sin\to -\cos\to \sin\to \cdots$。

    取 $x_0=0$，则 $\sin (x_0)=0, \cos(x_0)=1$，在 $\sin (x)$ 展开式中，就只有奇数次项是与 $\cos$ 有关的，而与 $\sin$ 有关的直接根据 $\sin(x_0)=0$ 忽略，在 $\cos(x)$ 中同理只有偶数次项和 $\cos$ 有关，所以：

两个幂级数的复合运算定义如下：

若 $A(x)=\sum\limits_{i=0}^{+\infty}a_ix^i, B(x)=\sum\limits_{i=0}^{+\infty}b_ix^i, C(x)=(B\circ A)(x)$ 或写作 $B(A(x))$，则：

注意，两个函数的复合有意义，当且仅当 $B$ 仅有有限多项，或 $a_0=0$。

有时我们会遇到这样的问题：给定一个幂级数 $B(x)\bmod x^n$，求出一个幂级数 $A(x)\bmod x^n$ 使得：

处理这样的问题的一种通用方法就是牛顿迭代法。

首先假设我们通过某种方式求出了 $n=1$ 时的答案（即确定了常数项），在实际运用中这通常是容易的。

当 $n>1$ 时，我们先递归求解出 $\lceil \dfrac{n}{2}\rceil $ 时的答案（接下来为了方便书写，省略了上取整），称为 $A_0(x)$，即：

接下来考虑对 $(B\circ A)(x)$ 这个复合函数在 $A_0(x)$ 处进行泰勒展开：

这个式子看似棘手，实际上方便处理。因为我们有 $A(x)\equiv A_0(x)\bmod x^{\frac{n}{2}}$（根据 $A_0(x)$ 的假设而来），移项后平方，得到：

因此上面的展开式中大于等于二次的项都可以忽略了（在 $\bmod x^n$ 意义下为 $0$），也就是说：

而条件是 $B(A(x))\equiv 0\bmod x^n$，所以：

这里面只有 $A(x)$ 是未知量，解得：

就建立了从 $A_0(x)$ 到 $A(x)$ 的过程，迭代这一过程即可求解原先的 $A(x)$。

常见运算

  1. 形式幂级数求逆。

    给定一个幂级数 $G(x)\bmod x^n$，求一个幂级数 $F(x)\bmod x^n$ 使得 $G(x)F(x)\equiv 1\bmod x^n$。

    不会 FFT 的做法：

    $[x^0]F(x)=\dfrac{1}{[x^0]G(x)}$，而通过 $x^m$ 项系数对比以及前面已经求出的项可以递推计算出 $[x^m]F(x)$，复杂度 $O(n^2)$。

    会 FFT 的做法：

    注意：$G(x)$ 可逆的条件是其常数项存在逆元，$[x^0]G(x)\ne 0$，那么 $F(x)$ 的常数项就是 $G(x)$ 的常数项的乘法逆元了，这是接下来迭代的下界。

    考虑先递归求出一个 $F_0(x)$ 使得：

    设 $H(F(x))=F(x)G(x)-1$，则我们要求的就是 $H(F(x))\equiv 0\bmod x^n$ 的 $F(x)$，直接套之前写过的牛顿迭代法的式子：

    考虑 $H’(F(x))=G(x)$，而因为泰勒展开中 $H’(F_0(x))$ 后的乘积项是 $(F(x)-F_0(x))\equiv 0\bmod x^{\frac{n}{2}}$，所以我们这里的 $H’(F_0(x))$ 在 $\bmod x^n$ 意义下只有前 $\dfrac{n}{2}$ 次项有意义，由于 $G(x)\equiv \dfrac{1}{F_0(x)}\bmod x^{\frac{n}{2}}$，所以可得：

    这样迭代的时间复杂度为 $O(n\log n+\dfrac{n}{2}\log \dfrac{n}{2}+\ldots)$，内部的和式不超过 $2n\log n$，所以该算法时间复杂度为 $O(n\log n)$。

  2. 形式幂级数对数函数（求 $\ln$）：

    给定一个幂级数 $G(x)\bmod x^n$，求出一个幂级数 $F(x)\bmod x^n$ 使得 $F(x)\equiv \ln(G(x))\bmod x^n$。

    这里的 $\ln(G(x))$ 就是 $G(x)$ 与 $\ln$ 的麦克劳林级数复合。

    注意，求 $\ln$ 时要求满足 $[x^0]G(x)=1$，否则会产生一系列问题。

    这个问题其实比较简单，我们将上面要求的式子两边同时求导：

    注意 $\ln’(x)=\dfrac{1}{x}$，而根据链式法则做复合函数求导时不要忘记 $G’(x)$。

    此时我们已经去掉了 $\ln$，然后两边积分还原 $F(x)$：

    注意常数项为 $\ln(1)=0$。

    于是我们先做一次求导，然后求一次逆，然后做一次多项式乘法，最后积分即可，时间复杂度为 $O(n\log n)$。

  3. 形式幂级数指数函数（求 $\exp$）：

    给定一个幂级数 $G(x)\bmod x^n$，求出一个幂级数 $F(x)\bmod x^n$ 使得 $F(x)\equiv \exp(G(x))\bmod x^n$。

    一种 $O(n\log^2 n)$ 或 $O(n^2)$ 做法：

    两边求导，建立递推式：

    直接递推复杂度为 $O(n^2)$，利用分治 FFT 的复杂度为 $O(n\log^2 n)$。

    正常的牛顿迭代：

    同理，这里的 $\exp(G(x))$ 就是 $G(x)$ 与 $\exp$ 的麦克劳林级数复合，且基于同样的理由，要求 $[x^0]G(x)=0$。

    考虑用牛顿迭代法解决这个问题，设 $H(F(x))=\ln (F(x))-G(x)$。

    直接带式子：

    而 $H’(F_0(x))=\dfrac{1}{F_0(x)}$，注意这里的求导仅仅是 $\dfrac{\mathrm{d}H}{\mathrm{d}F_0}$，所以不用链式法则。

    于是我们有：

    最后一个式子就是我们的目标，按照它迭代运算即可，时间复杂度分析和求逆类似，是 $O(n\log n)$。

  4. 形式幂级数幂函数：

    给定一个幂级数 $G(x)\bmod x^n$ 和实数 $k$，求出一个幂级数 $F(x)\bmod x^n$ 使得 $F(x)\equiv G^k(x)\bmod x^n$。

    思路一：倍增快速幂。

    当 $k\in \Z^+$ 时，我们只要用倍增快速幂，每次计算一次多项式乘法即可，时间复杂度为 $O(n\log^2 n)$。

    思路二：转化为 $\ln$ 和 $\exp$。

    将要求的式子两边 $\ln$，得到：

    再 $\exp$ 回去，就得到：

    所以我们做一次 $\ln$ 和一次 $\exp$ 即可。

    但是事情还没完，我们之前说过能做 $\ln$ 的条件是常数项为 $1$，如果常数项不为 $1$，就不能直接这样做。

    当然这个也很好处理，设 $a_ix^i$ 是 $G(x)$ 中的最低非零项，那么 $\dfrac{G(x)}{a_ix^i}$ 就是一个常数项为 $1$ 的幂级数了，我们将上面的式子稍作改写：

    这就解决了常数项不一定为 $1$ 的问题。

    这个做法的时间复杂度为 $O(n\log n)$。

生成函数

对于数列 $f_n (n\in \mathbb{N})$，定义其普通型生成函数（OGF）为：

定义其指数型生成函数（EGF）为：

生成函数是描述一个数列的方式之一，是解决数列问题的有用工具。

对数列的操作和变化，以及对数列的研究，可以用生成函数的运算和性质来刻画。

组合意义

记两个数列 $f_n (n\in \mathbb{N}), g_n (n\in \mathbb{N})$ 的 OGF 为 $F(x), G(x)$，其中 $f_i$ 表示：用 A 方法选出 $i$ 个元素的方案数，$g_i$ 则表示：用 B 方法选出 $i$ 个元素的方案数。

考虑一个新数列 $h_n (n\in \mathbb{N})$，其 OGF 满足 $H(x)=F(x)\times G(x)$，考虑 $h_i$ 的组合意义：

根据 OGF 的定义我们知道：

而最后的 $f_ig_{n-i}$ 可以理解为：用 A 方法选出 $i$ 个元素，再用 B 方法选出 $n-i$ 个元素的方案数，再加上枚举 $i$，相当于就是：总共选出 $n$ 个元素的方案数，无论分别用 A,B 方法选了几个。

注意这里的元素是无标号的，也就是我们不考虑 $n$ 个元素排列的顺序。

所以我们可知，两个数列 OGF 相乘的组合意义是：用两种方式共选出某一数量的无标号元素（的方案数）。

接下来再考虑两个数列的 EGF，也记作 $F(x),G(x)$。

考虑一个新数列 $h_n (n\in \mathbb{N})$，其 EGF 满足 $H(x)=F(x)\times G(x)$，考虑 $h_i$ 的组合意义。

先写出 $h_n$ 的表达式：

而如果我们将 $n!$ 与 $i!(n-i)!$ 组合，发现这是一个二项式系数，所以：

这个式子称为 二项卷积，其组合意义可以理解为：在 $n$ 个元素中，选出 $i$ 个用 A 方案选，另外 $n-i$ 个用 B 方案选，但和 OGF 不同的是，我们发现这里的元素是有标号的，也就是我们需要考虑用 A 方案选的元素和用 B 方案选的元素的先后次序。

所以我们可知，两个数列 EGF 相乘的组合意义是：用两种方式共选出某一数量的带标号元素（的方案数）。

那么如果是两个相同的生成函数相乘，又有什么特殊的组合意义呢？考虑 $F^2(x)$ 的组合意义，以同一方式取两次，共取走了 $n$ 个元素，我们将这个二次推广到 $n$ 次可知：$F^n(x)$ 的组合意义就是以统一方式共取 $n$ 次元素，总共取到某一数量元素的方案数，有无标号根据 EGF 还是 OGF 来决定。

注意指数上这个“取的次数”是带标号的，例如第一次取一个，第二次取两个和第一次取两个，第二次取一个是不同的取法。

我们可以更进一步，设两个 OGF 分别为 $A(x),B(x)$ 的无标号组合类 $S,T$，其中大小为 $i$ 的对象分别有 $a_i,b_i$ 个，设 OGF 为 $C(x)$ 的无标号组合类 $R$ 满足：

  • 每个对象是 $S$ 或 $T$ 中的对象：$C(x)=A(x)+B(x)$；

  • 每个对象是 $S,T$ 中各取一个的笛卡尔积：$C(x)=A(x)\times B(x)$；

  • 每个对象是 $S$ 中若干个对象组成的序列（带标号组合）：$C(x)=\sum\limits_{i=0}^{+\infty} A^i(x)=\dfrac{1}{1-A(x)}$；

  • 每个对象是 $S$ 中若干个对象组成的多重集（无标号组合）：

    这个操作称为欧拉变换，记为 $\mathcal E(A(x))$，会发现这其实就是一个完全背包，考虑 DP 过程，对每个物品相当于给答案的 OGF 乘上 $(1+x^i+x^{2i}+\ldots)$，所以：

  • 每个对象是 $S$ 中若干个对象的不可重集：

    和上面类似，只不过是 $01$ 背包：

  • 每个对象是 $S$ 中某个对象中的所有元素替换为 $T$ 中的一个对象：

    通常用于递归结构，不难发现这就是复合运算：

计算方法：

对于前三条都可以直接计算。

四五条的乘积式的常见处理手法是化乘为加，例如：

而复合的计算比较复杂，然而通常可以使用拉格朗日反演之类的方法搞。

对于带标号的组合类（下面的 GF 默认为 EGF），前三种操作是一样的，需要讨论的只是集合。

由于是带标号，所以没有“不可重集”这种说法，我们要解决的只是物品带标号的对象的无标号组合。

枚举对象的数量 $i$，由于组合无标号所以要去掉 $i!$，因此答案是：

上面所说的未免都有些抽象，接下来举几个相对具体的例子。

例题 $22$：[Luogu P4389] 付公主的背包

有 $n$ 个物品，第 $i$ 个大小为 $v_i$，有无限件，对每个 $i\in [1,m]$，求选择一些物品大小和为 $i$ 的方案数，不区分放入物品顺序。

大小和为 $i$，没有规定每一份“大小”的编号，所以对象内本身是无标号的。

不区分物品放入顺序，所以组合也是无标号的。

所以使用 OGF 的欧拉变换即可，时间复杂度 $O((n+m)\log m)$。

例题 $23$：[Luogu P5748] 集合划分计数

求出 $\text{Bell}(n)$，表示将集合 $\{1,2,\ldots,n\}$ 划分为若干个无标号非空子集的方案数。

集合是 $\{1,2,\ldots,n\}$ 本身有标号，所以是 EGF。

划分成无标号子集，所以组合是无标号的。

所以使用 EGF 做 $\exp$，我们只需要求出非空子集的 EGF，而这里 $\{1,\ldots,i\}$ 就这一种集合，所以是 $\sum\limits_{i=1}^{+\infty}\dfrac{x^i}{i!}=\exp(x)-1$，所以答案：

这就是 Bell 数的 EGF。

时间复杂度为 $O(n\log n)$。

例题 $24$：[CF 438 E] The Child and Binary Tree

求有多少点带权二叉树，点权在给定集合 $S$ 中（$|S|=n$），且所有点的点权和为 $m$，二叉树点无标号，但区分左右儿子。

定义二叉树的大小为其点权和，设二叉树的 OGF 为 $F(x)$，再设给定集合 $S$ 的 OGF 为 $G(x)$。

考虑根结点，可以分成左右儿子递归，它们的 OGF 也都是 $F(x)$，加上根结点的点权就有：

最后的 $+1$ 是递归边界：没有根结点的空树。

这是一个关于 $F(x)$ 的二次方程，解之：

出现两解，我们带入常数项检验，即求 $F(0)$，可以用洛必达求出（或者上下看看直接毛估估），只有取减号才满足我们的要求。

但是 $2G(x)$ 常数项为 $0$ 不方便求逆，我们可以直接上下同除掉最低次项，也可以分子有理化：

时间复杂度为 $O(n\log n)$。

例题 $25$：十二重计数法 X

求将 $n$ 划分成 $m$ 个无序自然数之和的方案数。

将问题转换一下，设 $t_x$ 表示划分出的不小于 $x$ 的数的数量，由于 $n=\sum\limits_{i=1}^{+\infty}[n\ge i]$，所以有 $n=\sum t_x$，而 $t_x$ 可以有任意多个，只要每个 $t_x$ 都在 $[1,m]$ 中（有 $0$ 可以直接拿走）。

因此问题变成了将 $n$ 拆分成若干个不超过 $m$ 的正整数之和，这就是欧拉变换：

时间复杂度为 $O((n+m)\log n)$。

简单的图计数

这里用生成函数解决一些比较简单的图计数问题，所有图默认为简单图。

树的计数可能需要用到 Prufer 序列等东西，以后再说。

  1. 无向图：$n$ 个点的带标号无向图数量为 $2^{\frac{n(n-1)}{2}}$；
  2. 有向图：$n$ 个点的带标号有向图数量为 $2^{n(n-1)}$；
  3. 竞赛图：$n$ 个点的带标号竞赛图数量为 $2^{\frac{n(n-1)}{2}}$。

例题 $26$：

求 $n$ 个结点的连通无向图数量，点带标号。

无向图可以看作连通无向图的带标号组合，设无向图的 EGF 为 $F(x)$，连通图的 EGF 为 $G(x)$，那么 $F(x)=\exp(G(x))$，所以 $G(x)=\ln(F(x))$。

时间复杂度为 $O(n\log n)$。

例题 $27$：

求 $n$ 个结点的强连通竞赛图数量，点带标号。

竞赛图可以看作强连通分量的序列，设竞赛图的 EGF 为 $F(x)$，强连通竞赛图的 EGF 为 $G(x)$，那么 $F(x)=\dfrac{1}{1-G(x)}$，所以 $G(x)=\dfrac{F(x)-1}{F(x)}$，注意 $[x^0]F(x)=1$。

时间复杂度为 $O(n\log n)$。

例题 $28$：

求 $n$ 个结点的二分图数量，点带标号。

设 $F(x),G(x)$ 分别为连通二分图和二分图数量的 EGF，$F_0(x),G_0(x)$ 分别是连通二分图和二分图给每个结点二染色使得相邻结点不同色的 EGF。

那么我们有：

最后一行是因为连通的二分图恰有交换两部颜色的两种二染色。

所以 $G(x)=\sqrt {G_0(x)}$，而 $\displaystyle [x^n]G_0(x)=\sum\limits_{i=0}^{n}\binom n i 2^{i(n-i)}$ 可以通过 FFT 算出。

注意这里一件有趣的事情：在计算 $G_0(x)$ 时由于 $\displaystyle i(n-i)=\binom n 2-\binom i 2-\binom {n-i}{2}$，所以我们实际上在用形如：

的生成函数做卷积，我不知道这东西有没有正式的名字，就姑且叫它“组合型生成函数”吧。

时间复杂度为 $O(n\log n)$。

例题 $29$：

求 $n$ 个结点的有向无环图数量，点带标号。

DAG 中剥掉所有没有入度的点仍得 DAG，这启发我们找出没有入度的点。

令 $f_n$ 表示答案，钦定 $x$ 个没有入度的点，这些点到其余点随便连边，然后容斥可以得到：

根据这个式子我们转化成生成函数，设两个前面所说的“组合型生成函数”：

所以有：

时间复杂度为 $O(n\log n)$。

例题 $30$：

求 $n$ 个结点的强连通有向图数量，点带标号。

设有向图的数量为 $f_n=2^{n(n-1)}$，强连通图的数量为 $g_n$，我们需要 $f,g$ 两个序列之间的关系。

但直接建立是困难的，我们考虑按照上题的方法，将有向图看作强连通分量构成的 DAG，然后同样容斥：

考虑这里的容斥系数 $h_n$ 的实际含义：将 $n$ 个点的图分成若干个强连通分量，如果奇数个则容斥系数为 $1$，偶数个则容斥系数为 $-1$。

考虑 $f,h$ 对应的“组合型生成函数” $F(x),H(x)$，我们可以知道：

接下来我们建立 $h,g$ 之间的关系，枚举 $1$ 所在的强连通分量：

于是设：

那么有：

时间复杂度为 $O(n\log n)$。

5. Burnside 引理

参考：https://www.luogu.com.cn/blog/Soulist/solution-p4980

提示：作者不会群论，证明可能是不严谨的，也不保证内容和记号恰当，如有错误烦请指出。

由于发现大纲里有 Burnside 和 Pólya 所以来紧急营业。

群和子群

考虑一个集合 $G$ 以及定义在 $G$ 上的二元运算 $\times$，如果满足下述条件，则称 $(G,\times)$ 是一个群：

  • 封闭性：$a,b\in G$，则 $a\times b\in G$；
  • 结合律：$a,b,c\in G$，则 $(a\times b)\times c=a\times (b\times c)$；
  • 存在单位元：$\exists e\in G$，$\forall a\in G, a\times e=e\times a=a$；
  • 每个元素可逆：$\forall a\in G$，$\exists b\in G, a\times b=b\times a=e$，称 $b=a^{-1}$。

例如，$(R\backslash\{0\},\times )$ 以及函数与其复合运算构成群。

当不要求存在单位元和逆元时，$(G,\times)$ 称为半群，例如 $(R,\max)$ 是半群。

当不要求存在逆元时，$(G,\times)$ 称为幺半群，例如 $(R,\times)$ 是幺半群。

当满足交换律 $a\times b=b\times a$ 时称 $(G,\times)$ 为交换群或阿贝尔群，例如 $(R,+)$ 是交换群。

一个群的单位元和每个元素的逆元都是唯一的。

考虑群 $(G,\times)$，如果集合 $H\subseteq G$ 且 $(H,\times)$ 是群，那么称 $(H,\times)$ 是 $(G,\times)$ 的子群。

可以证明，如果 $a\in H$，那么 $a^{-1}\in H$，并且单位元 $e\in H$。

对于子群 $(H,\times)$，令 $gH=\{g\times h|h\in H\}$ 为 $H$ 关于 $g$ 的左陪集，类似地定义右陪集 $Hg=\{h\times g|h\in H\}$，其中 $g\in G$。

下面说明一条关于陪集的重要性质（都以右陪集为例）：

  • 若 $Hg_1\cap Hg_2\ne \varnothing$，则 $Hg_1=Hg_2$。

假设 $g\in Hg_1\cap Hg_2$，那么设 $g=h_1\times g_1=h_2\times g_2$，考虑一个 $g’=h_3\times g_1\in Hg_1$，则 $g’=h_3\times (h_1^{-1}\times h_1)\times g_1=(h_3\times h_1^{-1})\times g=(h_3\times h_1^{-1}\times h_2)\times g_2\in Hg_2$，同理可以证明 $Hg_2\subseteq Hg_1$，因此我们得到了 $Hg_1=Hg_2$。

同时我们需要一则比较容易的性质：

  • $|H|=|Hg|$，这是因为假设存在 $h_1\times g=h_2\times g$，那么两边乘 $g^{-1}$ 得到了 $h_1=h_2$。

根据上面的两条性质，我们可以知道一个子群关于 $G$ 所有元素的陪集的结构：

$H$ 关于 $G$ 中元素的陪集共有 $\dfrac{|G|}{|H|}$ 种，两两不交且大小均为 $|H|$。

将这个陪集的种类数记为 $[G:H]$，根据上面的推导有 $|H|\times [G:H]=|G|$。

轨道-稳定子定理和 Burnside 引理

把由作用于集合 $F$ 上的变换构成的群称作变换群，例如实变函数与其复合运算构成的群就是作用在 $R$ 上的变换群。

也就是说，对于群 $(G,\times)$，任取 $g\in G$，都是形如 $g:F\to F$。

轨道：对于一个 $f\in F$，定义其在 $G$ 作用下的轨道为所有 $g(f) (g\in G)$ 的集合，记为 $G(f)$。

稳定子：对于一个 $f\in F$，定义其在 $G$ 作用下的稳定子是所有满足 $g(f)=f$ 的 $g$ 构成的集合 $G^f$。

那么我们有如下定理：

轨道-稳定子定理：$|G(f)|\times |G^f|=|G|$。

这个定理的证明依赖于上面写的陪集的性质：

首先是一个简单的命题：$(G^f,\times)$ 是 $G$ 的一个子群，因为如果 $g_1(f)=g_2(f)=f$，那么 $(g_1\times g_2)(f)=f$，并且 $g_1^{-1}(f)=f$。

所以实际上我们只需要证明：$[G:G^f]=G(f)$。

可以这么理解：所有 $g(f)$ 相同的 $g$ 构成了若干个等价类，每个等价类中作用于 $G^f$ 的陪集都相等，所以等价类数等于 $[G:G^f]$。

若对于两个元素 $f_1,f_2\in F$，使得存在 $g\in G$ 使得 $g(f_1)=f_2$，则称 $f_1,f_2$ 在 $G$ 作用意义下等价，设 $|F/G|$ 为这个等价类的个数。

Burnside 引理给出了计算 $|F/G|$ 的一个方法：

其中 $|F^g|$ 是满足 $g(f)=f$ 的不动点 $f$ 的个数。

证明：

考虑如何描述 $|F/G|$，由于每个轨道上的 $f$ 互相等价，所以只要求出轨道数量，而一个大小为 $S$ 的轨道可以由每个元素贡献一个 $\dfrac{1}{S}$，因此就有：

再套用轨道-稳定子定理：

于是 Burnside 引理得证。

置换群和 Pólya 定理

最常见的变换群之一就是置换群，作用于 $n$ 元集上的置换群可以看作若干个 $1,\ldots,n$ 的排列构成的群，运算为排列的复合，将排列 $a_1,\ldots,a_n$ 作用于元素 $f$ 就相当于将 $f$ 中的第 $i$ 个元素转移到 $a_i$ 处。

考虑如下问题：

给定 $n$ 元置换群 $G$ 和一个整数 $m$，令 $F$ 是将 $1,\ldots,n$ 中每个元素染上 $m$ 种颜色之一的所有 $m^n$ 种方案构成的集合，求 $|F/G|$。

可以直接套用 Burnside 引理，我们要求的就是 $|F^g|$。

而如果 $f$ 是 $g$ 作用下的一个不动点，那么对于置换 $g$ 中每个循环圈，$f$ 中这些位置的颜色必须都相等，所以我们相当于只能给每个循环圈一个颜色，所以 $|F^g|=m^{\operatorname{cyc}(g)}$，其中 $\operatorname{cyc}(g)$ 为置换 $g$ 的循环圈个数，带入 Burnside 引理得到：

这就是 Pólya 定理。

例题 $31$：[Luogu P4980] Pólya 定理

求给 $n$ 元环每个点染 $n$ 种颜色中一种的本质不同方案数，能旋转互相得到的算作等价。

本题中置换群为 $G=\{[1,2,\ldots,n],[2,3,\ldots,n,1],\ldots,[n,1,\ldots,n-1]\}$，而 $\operatorname{cyc}([i,i+1,\ldots,n,1,\ldots,i-1])=\gcd(i-1,n)$，因此运用 Pólya 定理知答案为：

分解素因数后搜索即可。

时间复杂度为 $O(\sqrt n)$。

例题 $32$：[HNOI 2009] 图的同构计数

求 $n$ 个点的本质不同无向图数量，同构的视作本质相同。

将边是否存在看作黑白两种颜色，此题中置换群 $G$ 包含所有 $n$ 元置换。

运用 Burnside 引理枚举 $g\in G$，设 $g$ 的所有循环圈大小依次为 $p_1,\ldots,p_m$，考虑跨越长度为 $p_i,p_j$ 两个循环圈中各一个点 $x,y$ 的边，设 $g=[g_1,\ldots,g_n]$，那么对于任意的 $g^z_x$ 和 $g^z_y$，它们之间边的颜色和 $x,y$ 相同，而容易知道两个循环圈上分别跑循环时的循环节长度是 $\operatorname{lcm}(p_i,p_j)$，所以循环圈个数 $\dfrac{p_ip_j}{\operatorname{lcm}(p_i,p_j)}=\gcd(p_i,p_j)$。

但是 $i=j$ 的情况有些特殊，环上所有跨度相等的边颜色都要相同，实际上是 $\lfloor\dfrac{p_i}{2}\rfloor$ 个等价类。

故对于确定的 $g$，其指数为：

在求得 $p_1,\ldots,p_m$ 后容易在 $O(\operatorname{poly}(n))$ 内求出。

而我们实际不必枚举所有排列，而只需枚举 $p_1,\ldots,p_m$ 的可重集，可以通过多项式系数乘圆排列并去重得到方案数。

所以枚举量实际是 $n$ 的正整数划分数 $p(n)$。

时间复杂度为 $O(p(n)\times n^2)$ 或更低。

例题 $33$：[MtOI 2018] 魔力环

给长度为 $n$ 的环二染色，使得不存在连续 $k+1$ 个黑点，求本质不同方案数，旋转等价。

类似例题 $31$，考虑直接使用 Burnside 定理，可以转化为：第 $i$ 个点和第 $i+d$ 个点颜色相同，并且没有连续 $k+1$ 个黑点的方案数。

那么整个环可以看作 $\dfrac{n}{d}$ 个小链粘合，可以发现不存在连续 $k+1$ 个黑点当且仅当小链不全为黑并且小链看作环时不存在连续 $k+1$ 个黑点。

前者是平凡的，我们计数后者，设 $f(d)$ 为长度为 $d$ 的环不包含连续 $k+1$ 个黑点的方案数，注意这里没有旋转等价的限制。

首先破环为链，首尾加起来不能超过 $k$ 个黑点，对此的特殊处理可以通过枚举首尾之和 $s$，再考虑中间，假设总共 $A$ 个白点（由于两边已经放好，所以此时一定有两个白点在两边，而 $A=1$ 也是平凡的）和 $B$ 个黑点，我们可以看成将 $B$ 个黑点插入 $A-1$ 个段并且每一段不大于 $k$ 的方案数，这是一个简单容斥，枚举有几个段爆了：

这里的时间复杂度实际上是 $O(\min(A,\dfrac{B}{k}))$，再加上前面枚举的前后之和 $\in[0,k]$，总共是 $O(B)$ 的，这里的 $B$ 是总黑点数，它等于 $\dfrac{m}{d}$。

由于 $d$ 必须同时是 $n,m$ 的因数，设 $d_0=\gcd(n,m)$，最后复杂度实际上是 $\sigma_1(d_0)$，它是 $O(d_0\log d_0)$ 的。

时间复杂度为 $O((n+m)\log (n+m))$。

6. 几个特殊数列

本段将介绍几个在计数问题中十分有用的数列或数阵以及它们的相关性质。

由于本篇文章以后会继续扩展（包括多项式部分以及其他一些组合工具），所以这里所写的主要服务于 NOI 大纲，较为简单。

卡特兰数

考虑如下问题：求包含 $n$ 个 $0$ 和 $n$ 个 $1$ 的序列个数，使得每个前缀中 $1$ 的个数不少于 $0$ 的个数。

这个问题可以描述成格路计数问题：从 $(0,0)$ 走到 $(2\times n,0)$，每一步可以由向量 $(1,1)$ 或 $(1,-1)$ 行进，求路径不经过 $y=0$ 下方区域的方案数。

将答案的个数记作卡特兰数 $Cat_n$，它的前几项是：$[1,2,5,14,42,\ldots]$。

我们这里介绍三种求其表达式的方法：

翻折法：

有点类似于中考经典题。

由组合数，总方案数为 $\displaystyle\binom {2n}{n}$，我们只需求出不满足的方案。

而不满足的情况一定是经过了直线 $y=-1$，下面我们给出一个更加广泛的命题：

从 $S(0,a)$ 走到 $T(n,b)$ 的，每次往右下或右上走，且触碰过直线 $y=c$ 的路径数量，等于从 $S’(0,2\times c-a)$ 走到 $T(n,b)$ 的同样要求的路径数（注意要求 $(c-a)(c-b)\ge 0$）。

取最早的与 $y=c$ 的交点，将之前的部分沿 $x=c$ 翻折，就得到了一一对应。

同样也可以翻折 $T$，结果都是将同侧转化为异侧的简单情况。

所以在求卡特兰数过程中经过 $y=-1$ 的路径数量就等于从 $(0,-2)$ 走到 $(2\times n,0)$ 的方案数，可以发现总共走了 $n+1$ 步左上和 $n-1$ 步左下，所以方案数是 $\displaystyle\binom {2n}{n-1}$。

所以卡特兰数为 $\displaystyle Cat_n=\binom {2n}{n}-\binom {2n}{n-1}$。

Raney 引理法：

我们首先要介绍如下定理：

Raney 引理：设有整数序列 $a_1,\ldots,a_n$ 满足 $\sum\limits_{i=1}^n a_i=1$，则它恰有一种循环同构序列满足所有非空前缀和均为正。

也考虑转化为格路问题，从 $(0,0)$ 走到 $(n,1)$，每一步沿着向量 $(1,a_i)$ 走一步。

从起点到终点拉一条线 $l:y=\dfrac{x}{n}$，不难发现前缀和均为正等价于折线完全位于该直线及更上方。

先随便找一个循环位移，再找一个位于 $l$ 下方且离 $l$ 距离最远的点 $A$，这个点以前部分路径称为 $P_1$，以后部分称为 $P_2$，那么 $P_2P_1$ 一定是合法的。

证明：我们直接把整条路径在 $(n,1)$ 后再复制一遍（一条从 $(n,1)$ 到 $(2\times n,2)$ 的路径），$A$ 点在复制后的位置为 $A’$，那么由于 $A$ 是离 $l$ 最远的点，所以 $AA’$ 必然是所有平行于 $l$ 的直线中最低的，所以从 $A$ 到 $A’$ 这一段路径满足题目要求。

如下图，最下方紫线为 $AA’$，可以发现其他紫线都在其上方（图片里的一些距离长短和位置是不准的，只是直观理解一下）：

那么这个 $A$ 是否唯一呢？由于 $l$ 的斜率是 $\dfrac{1}{n}$，所以如果有两个整点离它同样远，那么横坐标差为 $n$ 的倍数，而在它下方的点横坐标在 $[2,n-1]$ 中，所以不可能有两个，$A$ 是唯一的。

那如果 $A$ 不存在呢？那么我们画出的就是唯一满足条件的折线了，实际上我们也可以将 $(0,0)$ 看作这个 $A$，而 $(n,1)$ 就是那个 $A’$，这是更严谨的说明。

由此我们证明了存在唯一的 $A$ 使得从它开始的循环同构序列所有非空前缀和为正，引理得证。

Raney 引理中提到的结构还有一个特殊结果：满足和为 $1$ 的整数序列的所有循环同构各不相同。

证明：假设有两个循环同构相同，我们可以导出序列有整周期，设周期完整出现 $d$ 次，一个周期中的和为 $s_0$，有 $ds_0=s$，所以 $d=1$，说明没有非平凡周期，也就是其实所有循环同构不同。

事实上，运用与 raney 引理类似的方法，我们可以得到 $n\perp m$ 时的 $(n,m)-\text{dyck}$ 路计数公式。

那么如何用该引理得到卡特兰数通项公式呢？

我们考虑包含 $n+1$ 个 $1$ 和 $n$ 个 $-1$ 的数列，它的总和是 $1$，对其运用 raney 引理得到其 $2n+1$ 个循环同构中恰有一个非空前缀和全正，所以满足 raney 引理条件的序列共有 $\dfrac{\binom {2n+1}{n}}{2n+1}$ 个。

由于前缀和都是正数，所以第一个数必然是 $1$ 而不是 $-1$，那么我们删除第一个数，就得到了一个包含 $n$ 个 $1$ 和 $n$ 个 $-1$ 的数列，每个前缀和非负，容易发现这就是卡特兰数的要求，所以：

得到了同样的结果。

生成函数法：

首先我们需要一个卡特兰数的递推公式：

其中 $Cat_0=1$。

这是因为，在折线模型中考察折线与 $y=0$ 的最左交点 $(2i,0)$，那么这之后的方案自然是 $Cat_{n-i}$，而由于我们钦定这是最左，所以这之前不能碰到 $y=0$，所以我们必须是 $(0,0)\to (1,1)\to (2i-1,1)\to (2i,0)$，而中间从 $(1,1)$ 到 $(2i-1,1)$ 也是一个卡特兰数的走法 $Cat_{i-1}$。

设卡特兰数的一般型生成函数为 $C(x)$，那么有：

这是一个二次方程，求解得到：

类似二叉树那题，可以用洛必达法则带入常数项检验，发现应该取减号。

接下来一步是展开 $\sqrt{1-4x}$，这需要借助我们之前所说的广义二项式定理：

而 $(0.5)^{\underline{i}}$ 在乘上 $2^i$ 后是个类似双阶乘的东西，我们尝试把它搞出来：

这里我们假设 $(-1)!!=1$，接下来我们把这堆东西带进 $C(x)$ 的表达式中：

那么我们其实已经有了 $Cat_n$ 的表达式，下面就是要把它化简一下变得好看一些：

这和我们之前方法得到的结果一样，也是 $\displaystyle\binom {2n}{n}-\binom{2n}{n-1}$。

接下来介绍的是卡特兰数在组合数学中一些比较典型的出现：

  • $n$ 个数依次排好，有一个初始为空的栈，每次选择弹出栈顶（如果栈非空）或者将当前最靠前的数入栈，最终得到的出栈序列数为 $Cat_n$。

    维护一个描述序列，进栈时记录 $1$，出栈时记录 $0$，每个前缀 $1$ 不能少于 $0$，所以与卡特兰数对应。

  • 顶点标号的凸 $n$ 边形的三角剖分数量为 $Cat_{n-2}$。

    考虑写出递推式，平移一下下标就可以得到卡特兰数。

  • $n$ 对括号的匹配括号串数量为 $Cat_n$。

    根据定义显然。

  • $n$ 个点的无标号有根二叉树个数为 $Cat_n$，左右儿子区分。

    根据递推式或生成函数得证。

  • $n$ 个点的无标号有根树个数为 $Cat_{n-1}$，儿子区分。

    考虑删除根结点后的括号序即可。

由此可见卡特兰数在推导一些无标号递归结构时的作用。

例题 $34$：[SCOI 2010] 生成字符串

求 $n$ 个 $1$ 和 $m$ 个 $0$ 组成的序列中有多少满足任意前缀中 $1$ 的个数不少于 $0$ 的个数。

将卡特兰数稍微扩展了一下，仍然可以使用翻折法解决问题。

  • 当 $n<m$ 时，显然答案为 $0$；

  • 当 $n\ge m$ 时，将问题转化为格路计数：从 $(0,0)$ 走到 $(n+m,n-m)$，只能向右上或右下走，且不经过 $y=-1$ 的方案数。

    所有方案是 $\displaystyle\binom {n+m}{m}$，而经过 $y=-1$ 的方案数相当于将 $(0,0)$ 翻到 $(0,-2)$，走到 $(n+m,n-m)$ 的方案数，这个过程需要向上 $n+1$ 次，向下 $m-1$ 次，也就是 $\displaystyle\binom {n+m}{m-1}$。

    所以答案为 $\displaystyle\binom {n+m}{m}-\displaystyle\binom {n+m}{m-1}$。

时间复杂度为 $O(n+m)$。

例题 $35$：

统计从 $(a,b)$ 走到 $(c,d)$，每一步向右上或右下，且依次经过直线 $y=a_1,y=a_2,\ldots,y=a_k$ 的方案数（也就是说存在一个路径上点的子序列依次在这些直线上）。

感谢机房最强数学战力 uwagjaynoi 指导！

这是翻折法的一个扩展，我们可以对一个折叠起来的折线进行“展开”。

令 $a_0=b,a_{k+1}=d$，我们考虑将整个走的过程分成 $k$ 段，第 $i$ 段是从 $a_i$ 走到 $a_{i+1}$，其纵坐标改变了 $|a_{i+1}-a_i|$。

我们只需保证这个纵坐标变化量不变即可，对于 $a_i>a_{i+1}$ 的情况我们把 $a_{i+1}$ 沿着 $a_i$ 翻折到 $2\times a_i-a_{i+1}$ 的位置，这样我们可以把折叠的部分不断展开，转化成 $a$ 递增的情形，然后直接求一个组合数就是答案了。

可以直接考虑总的纵坐标变化量，所以答案就是：

时间复杂度为 $O(c-a)$。

例题 $36$：THUSC 2021 题目来自民间

建立 $70$ 个点的无标号的区分儿子的有根树与不大于 $Cat_{69}$ 的正整数之间的双射。

求删除根后的括号序列，本质上我们需要压缩括号序列。

直接根据字典序压缩，我们需要 DP 出给定一个前缀后还有多少种合法的括号序列，也可以根据翻折法直接计算（应该就是例题 $34$ 的结果）。

斐波那契数

斐波那契数列是在 OI 中比较常用，也有较多性质的一个线性递推数列，其定义如下：

它的前几项是 $[1,1,2,3,5,8,13,21,34,\ldots]$，有时我们也可以反向递推，例如 $Fib_0=0, Fib_{-1}=1$。

首先我们研究它的通项公式，它是二阶常系数齐次线性递推，我们有理由相信它有一个简洁的表达式。

考虑其生成函数 $F(x)$，由递推式可以知道 $F(x)$ 与 $xF(x)+x^2F(x)$ 大致相等，只是差了个一次项，需要补一个 $x$：

最后一步找出了 $x^2+x-1=0$ 的两个根，然后待定系数 $A,B$，我们解一解，具体过程省略，得到答案如下：

也就得到了斐波那契数列的通项公式：

我们当然可以用矩阵快速幂等方法计算斐波那契数列第 $n$ 项，但作为一个线性递推数列，我们可以研究它在模意义下的周期。

斐波那契循环节证明非常复杂，这里暂时只给出部分结论：

结论 $1$：斐波那契数列 $\bmod m$ 的周期不大于 $6\times m$。

结论 $2$：斐波那契数列 $\bmod 5$ 的最小正周期为 $20$。

结论 $3$：斐波那契数列 $\bmod p$（$p$ 是素数且 $p\equiv \pm 1\bmod 5$）的最小正周期是 $p-1$ 的因数。

结论 $4$：斐波那契数列 $\bmod p$（$p$ 是素数且 $p\equiv \pm 2\bmod 5$）的最小正周期是 $2p+2$ 的因数。

结论 $5$：设斐波那契数列 $\bmod p$（$p$ 是素数）的最小正周期为 $per$，则 $\bmod p^k$ 的最小正周期是 $p^{k-1}per$ 的因数。

结论 $6$：设斐波那契数列 $\bmod p_i^{c_i}$（$p_i$ 是两两不同的素数）的最小正周期为 $per_i$，则 $\bmod \prod p_i^{c_i}$ 的最小正周期是 $\operatorname{lcm}(per_1,per_2,\ldots)$。

根据结论 $1$ 我们可以知道最小循环节的大致范围，根据结论 $2$ 到 $4$ 可以知道模素数的循环节，结合 $5,6$ 可以得到模任意数的一个循环节（在各步取因数过程中都直接取自身，就可以得到一个合法循环节）。

事实上对于一般的二阶常系数齐次线性递推数列，结论 $5,6$ 也是成立的，但 $2,3,4$ 需要涉及二次剩余和特征根。

例题 $37$：[NOI 2011] 兔农

设数列 $f_i$ 满足：

  • $f_1=f_2=1$；
  • $f_i=f_{i-1}+f_{i-2} (i>2, f_{i-1}+f_{i-2}\not\equiv 1\bmod k)$
  • $f_i=f_{i-1}+f_{i-2}-1 (i>2, f_{i-1}+f_{i-2}\equiv 1\bmod k)$

求第 $n$ 项对 $p$ 取模的结果。

这是一个变形的斐波那契数列，当出现 $\bmod k=1$ 的数就会减去 $1$。

考虑 $f_i\equiv a\bmod k$，根据斐波那契循环节的结论，我们知道所有斐波那契数列中 $\bmod k$ 可能的结果都在前 $6\times k$ 项中出现，我们暴力递推就可以找到第一个满足条件的数。

将 $f_i\bmod k$ 这个数列按 $0$ 分段，那么显然某一段的第一个数是上一段的倒数第二个数 $x$，并且这一段会变成 $0$ 则有 $xf_i\equiv 1\bmod k$ 即 $f_i\equiv x^{-1}\bmod k$（如果本身就是 $xf_i\equiv 0\bmod k$ 我们可以不管，因为和正常斐波那契数列递推一样）。

如果 $x$ 不存在逆元或不存在 $f_i\equiv x^{-1}$，那么数列接下来的部分全都是 $xf_i$，直接矩阵快速幂计算。

否则，找到第一个满足 $f_i\equiv x^{-1}$ 的 $i$，后一个就是 $0$。

于是我们会发现 $x$ 也是循环的，只要找到了 $x$ 的循环节就掌握了整个数列的循环节，而由于某个 $x$ 仅仅由上一个 $x$ 决定，所以循环节长度显然是 $O(k)$。

整个数列的循环节知道以后以循环为整体做矩阵快速幂即可。

所以我们在 $O(k\log k+\log n)$ 复杂度内解决这个问题。

例题 $38$：[WC 2021] 斐波那契

设数列 $F_i$ 满足：

  • $F_0=a, F_1=b$；
  • $F_i=(F_{i-2}+F_{i-1})\bmod m (i\ge 2)$

求最小的 $p$ 使得 $F_p=0$。

有 $T$ 组询问（$T$ 不是小常数），每组询问给定 $a,b$，而 $m$ 是始终不变的。

我去找找讲题 ppt，感觉和题解做法不一样。

例题 $39$：[JOISC 2021] Ancient Machine

通信题。

Alice 得到一个由 $n$ 个字符 $\text{X,Y,Z}$ 构成的序列，Bob 需要给定一个 $1,\ldots,n$ 的排列，按照排列顺序删除字符，要求使得“删除 $\text{Y}$ 时其前驱后继分别为 $\text{X,Z}$”的情况出现最多，Alice 只能给 Bob 发送 $70000$ 个 bit，$n=10^5$。

考虑维护一个栈，记录第一个 $\text{X}$ 的位置，对于此后，遇到一个 $\text{X}$ 或 $\text{Y}$ 就进栈，遇到一个 $\text{Z}$ 就不断弹栈直到剩下最后一个 $\text{X}$，然后删掉这个 $\text{Z}$。

将 $\text{X,Y}$ 记作 $0$，将 $\text{Z}$ 记作 $1$，我们需要 $n+C$ 个 bit。

考虑序列中如果有些相邻的 $\text{Z}$，那么只留最后一个，其他全当成 $\text{X,Y}$ 进栈也没关系，所以我们可以把序列变成一个不包含连续 $1$ 的序列。

对于一个不包含连续 $1$ 的序列，我们有一种斐波那契编码可以将它的长度压缩。

斐波那契编码用一个 $0,1$ 串表示一个整数，右数第 $i$ 位的位权是 $Fib_i$，这个编码的特点是不含连续的 $1$（可以找到最靠前的两个连续 $1$ 进位）。

因此这题里需要的序列可以被看做斐波那契编码，从而将其表示的值转化为一个二进制整数来传输，这样长度是 $\log_2 Fib_n+C$。

实现时，可以对序列分段，将六十多个位分为一段用斐波那契编码转换二进制，可以通过本题。

时间复杂度为 $O(n)$。

斯特林数

定义第一类斯特林数 $S_1(n,m)$ 表示将 $n$ 个带标号元素分入 $m$ 个无标号圆排列的方案数。

定义第二类斯特林数 $S_2(n,m)$ 表示将 $n$ 个带标号元素分入 $m$ 个无标号非空集合的方案数。

定义上升幂 $n^{\overline{m}}=\prod\limits_{i=n}^{n+m-1}i$，定义下降幂 $n^{\underline{m}}=\prod\limits_{i=n-m+1}^n i$。

第一类斯特林数有递推式：

组合意义：加入第 $n$ 个元素时，要么新建一个圆，要么插入原有 $n-1$ 个元素其中一个的右手边。

第二类斯特林数有递推式：

组合意义：加入第 $n$ 个元素时，要么新建一个集合，要么插入一个原有的集合。

下降幂和上升幂可以互相转化，具体地：

下面需要说明斯特林数和各种幂之间的关系：

性质 $1$：第一类斯特林数和上升幂：

证明：第一类斯特林数 $S_1(n,m)$ 的递推式可以看成 $1,\ldots,n-1$ 的 $n-m$ 次初等对称轮换多项式的值，也就是从 $1,\ldots,n-1$ 中选出 $n-m$ 个数相乘的积相加的结果，这和 $x^{\overline{n}}$ 中 $x^m$ 项系数意义相同。

如果用式子说明，可以归纳，当 $n=0$ 时成立，否则：

性质 $2$：第二类斯特林数和下降幂：

证明：考虑组合意义，左边是把 $n$ 个带标号球放到 $x$ 个带标号盒子的方案数，右边枚举了非空盒子的个数 $m$，并依次从 $x$ 个盒子中选出 $m$ 个盒子（$x^{\underline{m}}=x(x-1)\ldots(x-m+1)$），并乘上无标号方案数 $S_2(n,m)$。

也可通过归纳证明，从略。

下面要介绍一个关于斯特林数的反演：斯特林反演。

它的结论如下：

上两式等价。

当然，这个式子也能轻松推导出两个斯特林数交换后的结果同样成立。

上面已经叙述了两类斯特林数在常幂和上升下降幂之间转换的重要作用，也许已经可以感知到两类斯特林数对应两种互逆的运算，下面我们稍微推一下式子来感受一下：

对比系数，就得到了一个重要的等式：

如果先代第一类后带第二类，得到的应该是差不多的结果：

将这个式子带入就可以证明斯特林反演公式：