组合数学与计数dp笔记

组合数学与计数dp学习笔记

前言：本文并非组合数学入门，难度大概为提高级到省选，请读者有一定的组合数学基础再阅读。本文为算法竞赛内容，尽量保证证明的严谨性，如有错误请指出。本文根据个人的学习顺序和喜好排列位置，不保证难度递增。

原本打算只做组合的，现在发现不加计数dp好像不大行。

标 * 表示我认为是好题。

更新中。

基础

一些组合数学的基础知识，这只是个备忘录。

容斥原理：

\[|A_1 \cup A_2 \cup \cdots \cup A_n | = \sum _{i=1} ^n |A_i| - \sum _{1\le i \lt j \le n} |A_i \cap A_j| + \cdots + (-1) ^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n | \]

一种常见的表现形式：

即 \(C[P]\) 为满足条件 \(P\) 的数量。

则 \(C[x=a] = C[x \le a] - C [x \le a-1]+ C[x \le a-2] - \cdots\)

\(\le\) 也可以为 \(\ge\)。

二项式定理：

\[(x+y) ^ n = \sum _{i=0} ^ n \binom n i x^i y^{n-i} \]

组合的恒等式，在此处积累：

\[\binom n m = \binom {n-1} {m-1} + \binom {n-1} m \]

组合意义证明，可以类似动态规划的思路。从 \(n\) 个物品中选 \(m\) 个，考虑最后一个物品选还是不选。如果最后一个物品选，则方案数为 \(\binom {n-1}{m-1}\)；如果不选，方案数为 \(\binom {n-1}{m}\)。

吸收恒等式：

\[\binom n k =\frac{n}{k} \binom {n-1}{k-1} \]

证明：展开即可

\[RHS=\frac{n}{k} \cdot \frac{(n-1)!}{(k-1)!(n-k)!} = \frac{n!}{k!(n-k)!} = \binom n k \]

\[\binom n m = \binom {n}{n-m} \]

组合意义证明：选 \(m\) 个物品和排除 \(m\) 给物品不选是等价的。

\[\binom n m \binom m k = \binom n k \binom {n-k} {m-k} \]

代数证明：

\[LHS = \frac{n!m!}{m! (n-m)! k! (m-k)!} = \frac{n!}{ (n-m)! k! (m-k)!}\\ RHS = \frac{n!(n-k)!}{k!(n-k)!(n-m)!(m-k)!} = \frac{n!}{(n-m)!k!(m-k)!} \]

组合意义：

以下由 \(|S|=n,|A|=m,|B|=k\)

左边表示从 \(S\) 中先选一个子集 \(A\)，再从 \(A\) 中选一个子集 \(B\) 的方案数。

右边表示从 \(S\) 中直接选一个子集 \(B\)，包含 \(B\) 的大小为 \(m\) 的集合 \(A\) 的个数之和。

意义相同。

\[\binom n m \binom {n-m} k =\binom n k \binom {n-k} m \]

组合意义：\(\binom n m \binom {n-m} k\) 是从一个大小为 \(n\) 集合中依次选两个不交的集合，大小分别为 \(m\) 和 \(k\)。我们改为先选 \(k\) 再选 \(m\) 可以得到 \(\binom n k \binom {n-k}m\)。

代数证明：

\[LHS = \frac{n! (n-m)!}{m! (n-m)! k!(n-m-k)!}= \frac{n!}{m! k!(n-m-k)!}\\ RHS = \frac{n! (n-k)!}{m! (n-k)! k!(n-m-k)!}= \frac{n!}{m! k!(n-m-k)!} \]

朱世杰恒等式：

\[\sum _{l=0} ^n \binom l k = \binom {n+1}{k+1} \]

组合意义证明：

从一个大小为 \(n+1\) 的集合 \(S=\{1,2,\dots,n,n+1\}\) 中选一个大小为 \(k+1\) 的子集，显然方案数为 \(\binom {n+1}{k+1}\)；考虑枚举其最大元素 \(m\)，则剩余的子集大小为 \(k\)，总方案数为 \(\sum \limits_{m=k+!} ^{n+1} \binom {m-1} k\)，令 \(l=m-1\) 即可得左式。

范德蒙恒等式：

\[\sum _{i=0} ^k \binom n i \binom m {k-i} = \binom {m+n} k \]

组合意义证明：

我们从大小为 \(n\) 的集合 \(A\) 和大小为 \(m\) 的集合 \(B\)（满足 \(A \cap B = \varnothing\)）的并集 \(A\cup B\) 中取 \(k\) 个元素，方案数显然为 \(\binom {n+m} k\)；而枚举每个集合中选了多少个元素可以得到 \(\sum _{i=0} ^k \binom n i \binom m {k-1}\)。

\[\sum _{j=0} ^m \binom {n+k-1} {k} = \binom {n+m} m \]

证明没想到什么比较好的办法，用的也比较少。

插板法

问题 1：

给你 \(n\) 个相同的球和 \(m\) 个不同的盒子，问有多少种办法把这 \(n\) 个球放进盒子？盒子不可以空。

直接插板法。

如下，一个 o 表示一个球，将板子 | 插到 o 之间。由于盒子不能为空，一个间隙只能插一个板子。总共有 \(n-1\) 个间隙，需要插入 \(m-1\) 个板子，总方案数位 \(\binom {n-1}{m-1}\)

o | o o o | o o o | o o 
1     2       3      4

问题2：

给你 \(n\) 个相同的球和 \(m\) 个不同的盒子，问有多少种办法把这 \(n\) 个球放进盒子？盒子可以空。

这个问题与上一个问题的区别在于一个间隙可以插多个板子，这样不好用组合数刻画。考虑借 \(m\) 个球，要求每个盒子至少有一个球。即转化为:

给你 \(n+m\) 个相同的球和 \(m\) 个不同的盒子，问有多少种办法把这 \(n+m\) 个球放进盒子？盒子不可以空。

这样可以得到答案为 \(\binom {n+m-1}{m-1}\)。

这样为什么是对的？考虑建立双射。对于满足原来的要求的方案，向每个盒子中额外的放一个球，可以唯一得到满足后者要求方案；而对于满足后者要求的方案，我们从每个盒子拿走一个球可以唯一地得到满足原来要求的方案。

问题3：HDU - 6397 Character Encoding

求不定方程 \(X_1 +X_2+ \cdots X_n =S\)，满足 \(X_1,X_2,\cdots X_n \in \mathbb{N}\) 且 \(X_1,X_2,\cdots X_n \le K\) 的解的个数。

去掉 \(X_i \le K\) 的限制可以转化为问题 2。

考虑容斥原理，我们假设至少有 \(i\) 个 \(X\) 超过了 \(K\)，记为 \(C[x=i]\)，则我们要求

\[C[x=0] = C [x \ge 0] -C[x \ge 1] + C[x \ge 2]+ \cdots (-1)^n C[x \ge n] \]

如何求 \(C[x \ge a]\)，我们选 \(a\) 个 \(X_i(X_i \gt K)\) 变为 \(X_i ^\prime =X_i -K -1\ge 0\)（这里产生了 \(\binom{n}{a}\) 的系数），则 \(X^{(\prime)}_1+X^{(\prime)}_2 + \cdots X^{(\prime)}_n=S - a (K+1)\)，故 \(C[x \ge a] = \binom{S-a(K+1)+n-1}{n-1} \binom {n}{a}\)。

问题4：Gym-104791B 810975 *

我们把输的看作分割符，连胜的场次看作变量，这样得到 \(X_1+X_2+\cdots + X_{n-m+1}=m\)，满足 \(X_i \in \mathbb N\) 且 \(\max \{X_i\} =K\)。转化为 \(C[x=0,X_i \le K] - C[x=0,X_i \le K-1]\)

卡特兰数与反射容斥

卡特兰数/单线反射容斥

卡特兰数意义众多，详见 Oi-wiki。

这里以路径计数为例。

我们要求 \((0,0)\) 到 \((n,n)\) 不越过 \(y=x\) 的路线数量。这等价与不触碰 \(y=x+1\)。我们考虑将触碰 \(y=x+1\) 的路线沿第一次触碰的位置翻折，则最后的终点为 \((n-1,n+1)\)。

考虑每一条 \((0,0) \to (n-1,n+1)\) 的路径和原来的路径有什么关系，建立双射。

  1. 对于每一条能够到达 \((n-1,n+1)\) 的路径，一定经过了 \(y=x+1\)，因为 \((0,0)\) 和 \((n-1,n+1)\) 位于 \(y=x+1\) 的两端。也就是说将其翻折后的路径一定能到达 \((n,n)\)，且一定不合法。
  2. 对于每一条到达 \((n,n)\) 但不合法的路径，一定有一个点触碰了 \(y=x+1\)，翻折后一定到达 \((n-1,n+1)\)。

这样 \((0,0) \to (n-1,n+1)\) 的路径与不合法的路径构成一一对应，集合大小相同。

这种方式可以称之为单线反射容斥。

故我们得到卡特兰数的一个通项公式：

\[C_n = \binom {2n}{n}-\binom{2n}{n-1} \]

除此之外卡特兰数还有如下表现形式：

定义式：

\[C_n = \begin{cases} 1, n=0\\ \sum _{j=0} ^{i-1} C_i C_{n-1+i}, n>0 \end{cases} \]

从组合角度证明定义式与第一个式子等价

考虑路径计数模型。

我们要求不越过 \(y=x\) 的路径的方案数，考虑其第一个触碰位置 \(y=x\) 的位置（除去 \((0,0)\)），不妨设为 \((a,a),1\le a \le n\)。

先考虑前半段，路径从 \((1,0) \to (a,a-1)\) 这一段一定不能触碰 \(x=y\)，其方案数为 \(C_{a-1}\)。

而后半段平移后等价与 \((0,0) \to (n-a,n-a)\)，方案数为 \(C_{n-a}\)

故总方案数为

\[\sum _{a=1} ^n C_{a-1} C_{n-a} = \sum _{i=1} ^{n-1} C_i C_{n-i+1} \]

组合数表示：

\[C_n = \frac{\binom{2n}{n}}{n+1} = \frac{(2n)!}{n!(n+1)!} \]

代数方法证明该式与第一个式子等价

\[\begin{align*} C_n &= \binom {2n}{n}-\binom{2n}{n-1}\\ &= \frac{(2n)!}{(n!)^2} - \frac{(2n)!}{(n+1)!(n-1)!}\\ &= (2n)! \frac{(n+1)!(n-1)!-(n!)^2}{(n!)^2(n+1)!(n-1)!}\\&=(2n)! \frac{(n+1)!(n-1)!-(n+1)!(n-1)!\frac{n}{n+1}}{(n!)^2(n+1)!(n-1)!}\\&=\frac{(2n)!}{(n!)^2(n+1)} \\&=\frac{(2n)!}{n!(n+1)!} \end{align*} \]

递推式：

\[C_n = \frac{4n-2}{n+1} C_{n-1} ,C_0=1 \]

代数法证明该式与第三个式子等价

\[\begin{align*} C_n &= \prod _{i=1} ^n \frac{4i-2}{i+1} \\ &= \prod _{i=1} ^n \frac{2i(2i-1)}{(i+1)i} \\&=\frac{\color {green} \prod \limits_{i=1} ^n 2i (2i-1)}{{\color{red} (\prod \limits_{i=1} ^n i)}{\color{violet} [\prod \limits_{i=1} ^n(i+1)]}} \\&= \frac{{\color{green} (2n)!}}{{\color{red} n!} {\color{violet} (n+1)!}} \end{align*} \]

红色和紫色那两项都是比较显然的，绿色那一项只需要注意到 \(2i\) 遍历了 \(1 \sim 2n\) 的所有偶数；\(2i-1\) 遍历了 \(1 \sim 2n\) 的所有奇数

P1641 [SCOI2010] 生成字符串

单线反射容斥板子。

将 \((n,m)\) 沿 \(y=x+1\) 翻折得到 \((m-1,n+1)\)，答案就是

\[\binom {n+m}{n} - \binom {n+m}{n+1} \]

关于直线对称的基础知识

\((x,y)\) 关于直线 \(y=x+k\) 的对称点为 \((y-k,x+k)\)。

P3978 [TJOI2015] 概率论

一道难度争议很大的题。因为是结论题。

大小为 \(i\) 的不同构的树有 \(f_i\) 个，它们的叶子节点总数为 \(g_i\)，显然期望为 \(\frac{g_n}{f_n}\)。

先考虑打一个表

\(i\) 1 2 3 4 \(\cdots\)
\(f_i\) 1 2 5 14 \(\cdots\)
\(g_i\) 1 2 6 20 \(\cdots\)

于是我们猜想：

\[f_i =C_i,g_i =i f_{i-1} \]

先考虑证明 \(f_i=C_i\)。由于左子树右子树是区分的，考虑枚举左右子树大小 。

\[f_i = \sum _{k=0} ^{i-1} f_k f_{i-1-k} \]

显然为卡特兰数定义式。

再考虑证明 \(g_i=i f_{i-1}\)。

  • 对于一个 \(n\) 个结点的二叉树 \(T\)，假设它有 \(k\) 个叶子结点，去掉某一个叶子结点后可以得到 \(T_1,T_2,\dots,T_k\) 这 \(k\) 个大小为 \(n-1\) 的二叉树；
  • 每个 \(n-1\) 个结点的二叉树，有 \(n\) 个位置可以挂一个叶子结点。（可以这么想，\(1\) 个结点的二叉树有 \(2\) 个位置可以挂叶子，每挂一个结点会占用 \(1\) 个原有的位置，同时增加两个挂再新增结点下面的位置。故 \(n\) 个结点的二叉树有 \(n+1\) 个位置可以挂叶子）

这样我们得到一个二分图状物，假设左部结点代表 \(n\) 个结点的二叉树，右部结点表示 \(n-1\) 个结点的二叉树，左右连边表示两棵树可以通过加或减叶子来建立联系。从右部点来看，每个右部点向右连出 \(n\) 条边，故这张图的总边数为 \(f_{n-1} \times n\)；从左部点来看，有一个叶子结点就会连出一条边，故这张图的总边数为 \(g_n\)。而这张图是确定的，故 \(g_n=n f_{n-1}\)。

期望为

\[\begin{align*} E &= \frac{g_n} {f_n} \\&=\frac{n f_{n-1}}{\frac{4n-2}{n+1} f_{n-1}}\\ &=\frac{n(n+1)}{4n-2} \end{align*} \]

这题体现了组合数对应的思想。一般是一一映射，但此题较为特殊，所以借用二分图。

双线反射容斥

考虑将上面单线的限制转化为双线的限制。

求从 \((0,0) \to (n,m)\) 的不触碰 \(L_1:y=x+a\) 和 \(L_2:y=x+b\) 路径数。（保证 \(a \gt 0,b \lt 0,b \lt m-n \lt a\)）。

考虑沿用上面的方法。

我们可以简单的计算出触碰 \(L_1\) 和 \(L_2\) 的路径数，但是这样会算重：一条路径可能既碰了 \(L_1\) 又碰了 \(L_2\)，这样会重复计算。考虑容斥，触碰 \(L_1\) 后又触碰 \(L_2\)，考虑两次翻折后的路径数。类似的，可以算出翻折三次的路径数。

不加证明地（因为我不会）给出结论：设 \(E_0\) 为最初起点，\(E_1\) 为 \(E_0\) 关于 \(L_1\) 对称点，\(E_2\) 为 \(E_1\) 关于 \(L_2\) 的对称点……\(E_{-1}\) 是 \(E_0\) 关于 \(L_2\) 的对称点，\(E_{-2}\) 是 \(E_{-1}\) 关于 \(L_1\) 的对称点，依次类推，，最终答案为 \(N(E_0) -N(E_1) +N(E_2) - \dots -N(E_{-1}) +N(E_{-2}) \dots\)，\(N(E)\) 为从 \((0,0) \to E\) 的路径数。复杂度为 \(O(\frac{n+m}{a-b})\)。

代码：

void rev(int &x,int &y,int a){
    swap(x,y);x-=a,y+=a;
}
unsigned solve(int n,int m,int a,int b){
    unsigned ans=0;
    int x,y,d;
    addmod(ans,get_C(n+m,m));
    x=n,y=m,d=1;
    while(x>=0&&y>=0){
        if(d) rev(x,y,a);
        else rev(x,y,b);
        if(d) submod(ans,get_C(x+y,x));
        else addmod(ans,get_C(x+y,x));
        d^=1;
    }
    x=n,y=m,d=1;
    while(x>=0&&y>=0){
        if(d) rev(x,y,b);
        else rev(x,y,a);
        if(d) submod(ans,get_C(x+y,x));
        else addmod(ans,get_C(x+y,x));
        d^=1;
    }
    return ans;
}

P3266 [JLOI2015] 骗我呢 *

骗你呢。

注意到很古怪的一点，\(x_{i,j}< x_{i,j+1}\)，而值域为 \([0,m] \cap \mathbb Z\)，说明每行有且仅有一个数没有出现。于是我们可以用没有出现的数表示一行的状态。

考虑动态规划。设 \(f_{i,j}\) 表示第 \(i\) 行及以前均合法，第 \(i\) 行每出现的数为 \(j\) 的方案数。手玩一下可以发现：

\[f_{i,j} = \sum _{k=0} ^{j+1} f_{i-1}{k} \]

类似完全背包的优化可以写成:

\[f_{i,j} = f_{i-1,j+1} + f_{i,j-1} (j>0)\\ f_{i,0} = f_{i-1,0} + f_{i-1,1} (j=0) \]

边界条件为 \(f_{1,x}=1,1<x<m\)，由于转移方程，与 \(f_{1,0} =1\) 等价。

答案为 \(\sum \limits_{j=0} ^m f_{n,m} = f_{n+1,m}\)。

空间、时间都爆炸了。但是系数非常简单，考虑放到平面上。

转移平面

有大量斜着的边，不好用组合表示。考虑将一些点平移。然后发现 \(A \to B \to I \to N\) 这一条路径还是斜的，建一些虚点。

平移后

这样我们将问题转化为双线反射容斥。

注意 \(A(1,0),J(1,m),W(n,n-1),T(n,m+n-1)\)，两条线分别为 \(y=x-3\) 和 \(y=x+m\)。然后平移得到终点 \((n-1,m+n)\)，两条线为 \(y=x-2\) 和 \(y=x+m+1\)

注意阶乘要处理到 \(3\times 10^6\)。

CCPC 2022 Guangzhou J. Math Exam *

\(m\) is odd.How odd!

当 \(i=1\) 时，\(S_i=a_i\)，则 \(4 a_1 = a_1 ^2 +2 a_1 +1\) 解得 \(a_1=1\)。

当 \(i=2\) 时，\(S_i=a_i+1\)，则 \(4 a_2 +4 = a_2 ^2 +2 a_2 +1\) 存在 \(a_2 =-1\) 和 \(a_2=3\) 两组解，没有继续尝试的必要了。

考虑推式子。

\[\begin{align*} 4 S_i &= a_i^2 + 2 a_i +1 \\ 4 S_i &= (a_i+1)^2 \end{align*} \]

注意前面隐藏了一个条件：\(S_i \ge 0\)。

由 \(S_i\) 为前缀和，

\[\begin{align*} 4 (S_{i-1}+a_i) &= (a_i+1)^2 \\ 4 S_{i-1}&=(a_i-1)^2 \end{align*} \]

所以

\[4S_i = (a_{i+1}-1)^2 \]

联立得

\[(a_i+1) = \pm( a_{i+1}-1) \Rightarrow a_i = - a_{i+1} / a_i +2 = a_{i+1} \]

不妨令 \(b_i = \frac{|a_i+1|}{2}\)，则 \(b_1=0,b_i =b_{i-1} \pm 1\)。

考虑 \(|a_i| \le m\)：

\(2b_i = |a_i+1|\)，故 \(\le b_i \le \frac{m+1}2\)

转化为这样的图：

图片3

终点为 \((n-1,x),x \in [0,\frac{m+1}{2}] \cap \mathbb Z\)。

大力转系，放缩，平移，得到 \(A(0,0)\)，\(B(1,0)\)，左边能碰到得直线为 \(y=x-1\)，右边能碰到的直线为 \(y=x+\frac{m-1}{2}\)，终点在 \(y=-x+{n}\) 上。由于两条直线间的距离为 \(O(m)\) 的，有效的点也是 \(O(m)\) 的，而计算一个点的复杂度为 \(O(\frac{n}{m})\) 故总复杂度为 \(O(n)\)

斯特林数

第一类斯特林数

表示 \(n\) 个不同元素构成 \(k\) 个互补区分的非空轮换的个数。轮换就是将元素排成环，如 \([1,2,3]\) 与 \([2,3,1]\) 是相同的轮换。

\[{n \brack k}={{n-1} \brack {k-1} }+(n-1){{n-1} \brack {k}} \]

解释：由于轮换是互补区分的，所以插在之前的某个轮换中可以定位为插在某个元素之后，共有 \(n-1\) 个，这部分贡献为 \((n-1){{n-1} \brack {k}}\)；另一种情况是新开一个轮换，这部分的贡献为 \({{n-1} \brack {k-1} }\)

第二类斯特林数

第二类斯特林数表示将 \(n\) 个不同元素划分成 \(k\) 个互不区分非空集合（顺序无关）的方案数。

\[{n \brace k }={n-1 \brace k-1}+k{n-1 \brace k} \]

解释：要么放入原来的集合，贡献为 \(k{n-1 \brace k}\)；要么新开一个。

重要公式：

\[m^n = \sum _{i=0} ^{\min \{m,n\}} {n \brace i} i! \binom m i = \sum _{i=0} ^m {n \brace i} m^{\underline{i}} \]

组合意义证明：

可以左边表示将 \(n\) 个互相区分的球分到 \(m\) 个可以为空的互相区分的盒子中；右边可以表示为枚举有 \(i\) 个非空盒子，选择 \(i\) 个盒子（\(\binom n i\)），将 \(n\) 个球分为 \(i\) 个非空集合（\(n \brack i\)），再区分地放入 \(i\) 个盒子中。

考虑一个题目：

CF622F The Sum of the k-th Powers

直接推式子。由于 \(k \lt n\)，把 \(\sum _{i=1} ^n\) 转化为 \(\sum _{i=1} ^k\)。

\[\begin{align*} \sum _{i=1} ^n i^k &= \sum _{i=1} ^n \sum _{j=0} ^k {k \brace j} j ! \binom i j \\&=\sum _{j=0} ^k j! {k \brace j}\sum _{i=1} ^n \binom i j\\&= \sum _{j=0} ^k j! {k \brace j} \binom {n+1}{j+1} \end{align*} \]

最后一步用到了朱世杰恒等式 \(\sum \limits_{l=0} ^n \binom l k = \binom {n+1}{k+1}\)。

利用生成函数和多项式可以快速求同一行/一列的斯特林数，暂且跳过。

CF1278F Cards *

单次抽到小丑牌的概率为 \(p = \frac{1}{m}\)。

抽到 \(i\) 第小丑牌的概率 \(P [x=i] = \binom {n}{i} p^i (1-p) ^{n-i}\)。

\(x ^ k\) 的期望为

\[\begin{aligned} E &= \sum _{i=0} ^ n P[x=i] i^k\\ &=\sum_{i=0} ^ n \binom n i p^i (1-p)^{n-i} i^k \\ &= \sum _{i=0} ^n \binom n i p^i (1-p)^{n-i} \sum _{j=0} ^k { k \brace j} j! \binom i j\\ &=\frac{1}{m^n}\sum _{j=0} ^k { k \brace j} j! \sum _{i=0} ^n \binom n i \binom i j (m-1)^{n-i} \\ &=\frac{1}{m^n}\sum _{j=0} ^k { k \brace j} j! \binom n j \sum _{i=j} ^n (m-1)^{n-i} \binom {n-j} {i-j} \\ &=\frac{1}{m^n}\sum _{j=0} ^k { k \brace j} j! \binom n j \sum _{i=0} ^{n-j} (m-1)^{i} \binom {n-j} {n-j-i}\\ &=\frac{1}{m^n}\sum _{j=0} ^k { k \brace j} j! \binom n j \sum _{i=0} ^{n-j} \binom {n-j} {i} (m-1)^{i}\\ &= \frac{1}{m^n}\sum _{j=0} ^k { k \brace j} j! \binom n j m^{n-j}\\ &= \frac{1}{m^n} \sum _{j=0} ^k {k \brace j} j! \frac{n!}{j! (n-j)!} m ^{n-j}\\ &= \frac{1}{m^n} \sum _{j=0} ^k{ k \brace j} n ^{\underline {j} } m^{n-j} \end{aligned} \]

推导用到了和式变换，恒等式 \(\binom n m \binom m k = \binom n k \binom {n-k} {m-k}\) 和二项式定理。

可以发现最后一步可以预处理下降幂和多项式轻松地做到 \(\Theta (k \log k)\)。

题组（一）

一些与组合数学相关，但是难以归类到前面的某一类知识点或综合考察多种知识的题目。

这一部分主要为计数 dp 与组合的巧妙结合。

AT_agc013_d [AGC013D] Piling Up （代表元思想，*）

设第 \(i\) 次操作后还有 \(a_i\) 个红积木，则 \(a_i \in [0,n] \cap \mathbb Z\)。

考虑依次操作后的变化：

  • 先拿出一个红的（\(a_i \ge 1\)）（暂时 \(a_{i+0.5} \gets a_i-1\)）
    • 再拿出一个红的，\(a_{i+1} = a_i-1\)；
    • 再拿出一个蓝的，\(a_{i+1} = a_i\)；
  • 先拿出一个蓝的（\(a_i \le n-1\)）（暂时 \(a_{i+0.5} \gets a_i\)）
    • 再拿出一个蓝的，\(a_{i+1} = a_i+1\)；
    • 再拿出一个红的，\(a_{i+1} = a_i\)。

有了这个我们可以动态规划了，设状态 \(f_{i,j}\) 为第 \(i\) 步操作后 \(a_i=j\) 的方案数。

但是这样有个问题，我们会算重。比如 \(n\) 足够大时，\(a_0=1,2,3,\dots\)，我们始终拿走一个红的，拿走一个蓝的，最后建出来积木顺序完全相同。

如何解决？我们的问题只与折线的形有关，与折线的具体位置无关。我们钦定当折线碰到 \(0\) 时计数即可。这就是代表元的思想，钦定再某个时候计算答案，避免算重或算漏。

CF1895F Fancy Arrays

小清新计数题。

\(x \le 40\) 非常古怪，大概率在这上面要做文章。

题目要求至少有一个值在 \([x,x+k-1]\) 之间的长度为 \(n\) 非负整数数组 \(a\) 的数量，结合 \(x\) 的古怪范围，可以想到一步容斥。即答案等于存在一个数小于 \(x+k-1\) 的数组数量减去所有数都小于 \(x\) 的数组数量。分别考虑。

  1. 存在一个数小于 \(x+k-1\) 的数组数量；
    由于题目限制了相邻两项之差，即差分数组的值域范围。显然，差分数组每一位一共存在 \(2k+1\) 种方案，总共有 \((2k+1)^{n-1}\) 种差分数组。而确定差分数组就确定了最小值的下标，枚举最小值又有 \(x+k\)。这样，我们可以求得这部分贡献为 \((x+K)(2k+1)^{n-1}\)。

  2. 所有数都小于 \(x\) 的数组数量；
    由于 \(x\) 很小，考虑 dp。设 \(f_{i,x}\) 为枚举到第 \(i\) 位，该位填 \(x\) 的方案数。转移是容易的。而 \(n\) 很大，矩阵加速即可。

AT_abc281_g [ABC281G] Farthest City *

题意：求有多少个 \(n\) 个无向单位权连通图，满足 \(n\) 到 \(1\) 的距离严格大于其他任意一个点到 \(1\) 的距离。模数不保证为质数。

由于所有边权都为 \(1\)，可以对图经行分层。我们可以发现，这 \(n\) 个点可以分为三类，\(1\)，\(2 \sim n\)，\(n\)。从分层的角度看，\(1\) 一定单独为一层；\(2\sim n\) 分成若干层，没有什么限制；\(n\) 一定为最后一层，接在最后一层之后。

设 \(f_{i,j}\) 为已经选了 \(i\) 个数，最后一层有 \(j\) 个点的方案数。边界条件为 \(f_{1,1}=1\)。答案为 \(\sum_{k=1}^{n} (2^k-1) f_{n-1,k}\)。

转移也是容易的，枚举倒数第二层的大小即可：

\[f_{i,j} \gets 2^{\binom{j}{2}} \sum _{k=1} ^ {i-j} {(2^k-1)}^j \binom {n-1-(i-j)}{k} f_{i-j,k} \]

外面的系数 \(2^{\binom{j}{2}}\) 是层内可以任意连边；\({(2^k-1)}^j\) 表示层间每个点至少向前一条边。

反演

此处特指组合中的反演，数论中的莫比乌斯反演等不会涉及。

先把反演的几个公式贡在这里。

反演是什么？

\[g(x) =\sum _{k} f(k) h(k,x) \Rightarrow f(x) =\sum _{k} g(k) h ^{-1} (k,x) \]

其中 \(h ^{-1} (k,x)\) 为 \(h(k,x)\) 的逆运算，等价于逆矩阵。

一般使用反演的题目中 \(g(x)\) 是好求的，而 \(f(x)\) 并不容易。

二项式反演：

\[g(n) = \sum _{i=0} ^n \binom n i f(i) \Rightarrow f(n)= \sum _{i=0} ^n (-1)^{n-i} \binom n i g(i)\\ g(k) =\sum _{i=k} ^n\binom i k f(i) \Rightarrow f(k) \sum _{i=k} ^ n \binom i k (-1)^{i-k} g(i) \]

子集反演：

\[g(S) = \sum _{T \subseteq S} f(S) \Rightarrow f(S) = \sum _{T \subseteq S} (-1)^{|S|-|T|} g(T) \]

min-max 反演（似乎更多的叫 min-max 容斥？）：

\[\max (S) = \sum _{T \subseteq S} (-1)^{|T|+1} \min (T) \]

该式常用于期望意义下：

\[E[\max (S)] = \sum _{T \subseteq S} (-1)^{|T|+1} E[\min (T)] \]

斯特林反演：

\[g(n)=\sum _{i=0} ^n {n \brace i} f(i) \Rightarrow f(n) = \sum _{i=0} ^ n (-1)^{n-i} {n \brack i} g(i)\\ g(n)= \sum _{i=n} ^ {\infty} {i \brace n } f(i) \Rightarrow f(n) = \sum _{i=n} ^ {\infty} (-1)^{k-n} {k \brack n} g(k) \]

二项式反演

最主要是这两个式子。

\[g(n) = \sum _{i=0} ^n \binom n i f(i) \Rightarrow f(n)= \sum _{i=0} ^n (-1)^{n-i} \binom n i g(i)\\ g(k) =\sum _{i=k} ^n \binom i k f(i) \Rightarrow f(k) =\sum _{i=k} ^ n \binom i k (-1)^{i-k} g(i) \]

证明

\[g(n) = \sum _{i=0} ^n \binom n i f(i) \Rightarrow f(n)= \sum _{i=0} ^n (-1)^{n-i} g(i) \]

考虑证明该式。

首先说一句废话：

\[f(n) = \sum _{m=0} ^ n [n-m=0] \binom n m f(m) \]

这个式子显然成立，因为只有当 \(n=m\) 时和式有贡献，而 \(\binom n m=1\)。

由二项式定理

\[\sum _{k=0} ^n (-1) ^k \binom n k =(1-1)^n = [n=0] \]

（组合数学中一般约定 \(0^0=1\)）

将第二个式子代入第一个式子，得

\[f(n) = \sum _{m=0} ^n \sum _{k=0} ^{n-m} (-1)^k \binom {n-m} k \binom {n}{m} f(m) \]

由恒等式 \(\binom n m \binom {n-m} k =\binom n k \binom {n-k} m\)，

\[f(n) = \sum _{m=0} ^n \sum _{k=0} ^{n-m}(-1)^k \binom n k \binom {n-k} {m} f(m) \]

一些和式变换：

\[f(n) =\sum _{k=0} ^n (-1)^k \binom n k {\color {red} \sum _{m=0} ^{n-k} \binom {n-k}{m} f(m) } \]

注意到：\({\color {red} \sum _{m=0} ^{n-k} \binom {n-k}{m}f(m)}\) 就是 \(g(n-k)\)：

\[f(n)=\sum _{k=0} ^n (-1)^k \binom n k g(n-k) \]

下标变换一下，且 \(\binom n {n-k} = \binom n k\)，

\[f(n)=\sum _{k=0} ^n (-1) ^{n-k} \binom n k g(k) \]

证毕！

\[g(k) =\sum _{i=k} ^n \binom i k f(i) \Rightarrow f(k) =\sum _{i=k} ^ n \binom i k (-1)^{i-k} g(i) \]

再来考虑证明这个。

我们考虑换种证法：直接将后者代入前者

\[\begin{aligned} g(k) &=\sum _{i=k} ^n \binom i k f(i) \\ &= \sum _{i=k} ^n \binom i k \sum _{j=i} ^n \binom {j}{i} (-1)^{j-i} g(j)\\&=\sum _{j=k} ^n g(j)\sum _{i=k}^j \binom j i \binom i k (-1)^{j-i} \\&=\sum _{j=k} ^ n g(j) \binom j k \sum _{i=k} ^ j \binom {j-k}{i-k } (-1)^{j-i} \\&= \sum _{j=k} ^n g(j) \binom j k \sum _{t=0} ^ {j-k} \binom {j-k} {t} (-1) ^{j-k-t}(t=i-k) \\ &= \sum_{j=l} ^ n g(j) \binom j k [j=k] \\&=g(k) \end{aligned} \]

证毕！

组合意义

我们再好好看看这两个式子。

\[g(n) = \sum _{i=0} ^n \binom n i f(i) \Rightarrow f(n)= \sum _{i=0} ^n (-1)^{n-i} g(i)\\ g(k) =\sum _{i=k} ^n \binom i k f(i) \Rightarrow f(k) =\sum _{i=k} ^ n \binom i k (-1)^{i-k} g(i) \]

先考虑一下左式会在什么情况下成立。

可以由容斥原理发现：

  • 当 \(g(n)\) 表示至多 \(n\) 个，\(f(n)\) 表恰好 \(n\) 个时，第一个式子成立。
  • 当 \(g(n)\) 表示至少 \(n\) 个，\(f(n)\) 表恰好 \(n\) 个时，第二个式子成立。

看几道题目：

P10596 BZOJ2839 集合计数

题意：求从 \(n\) 个元素的集合的 \(2^n\) 个子集中取若干个集合，其交集元素个数为 \(k\) 的集合的个数。

由于元素个数恰好为 \(k\) 比较严格，考虑放宽限制。

考虑交集至少为 \(k\) 的方案数，可以写出 \(\binom {n}{k} (2^{2^{n-k}}-1)\)，\(\binom n k\) 表示选定一个集合，\(2^{n-k}\) 表示包含该集合的一共有这么多个，这些集合可以选任意个，但不能都不选。

那么已知 \(g(k)\)，求 \(f(k)\) 套第二个公式即可。

P4859 已经没有什么好害怕的了 *

题意：给定两个长度均为 \(n\) 数组 \(a_i,b_i\) 满足 \(\forall 1 \le i,j\le n,a_i \neq b_j\)。求有多少种 \(a_i\) 与 \(b_i\) 的两两匹配方式（\(a_i\) 与 \(b_{c_i}\) 匹配，\(c_i\) 为 \(1 \to n\) 的一个排列），满足 \(a_i>b_{c_i}\) 的对数比 \(a_i<b_{c_i}\) 小的对数多 \(k\)。

依题意

\[\begin{cases} [a \gt b] + [a \lt b] =n\\ [a \lt b] - [a \gt b] =k \end{cases} \]

解得 \([a \gt b]=\frac{n+k}{2}\)。

当 \(n+k\) 为奇数时直接无解。

当 \(n+k\) 为偶数时，令 \(m= \frac{n+k}{2}\)，需要继续讨论。

不妨先排个序，令 \(a_1 \lt a_2 \lt \cdots \lt a_n,b_1 \lt b_2 \lt \cdots \lt b_n\)。恰好有 \(m\) 对 \(a>b\) 限制较严。所以先考虑放松限制。

我们来分析一下这个问题，一个 \(a_i\) 选择了一个比自己小的数，显然 \(a_j,j>i\) 都少了一个机会；而选择一个比自己大的数，对于后面的影响就不知道了。

所以我们考虑至少有 \(m\) 对 \(a>b\)。

考虑 DP。设 \(f_{i,j}\) 为前 \(i\) 个数中我们已经钦定了 \(j\) 个数选择比自己小的数的选择的 \(j\) 的集合的数量，则可以得到转移方程

\[f_{i,j} \gets f_{i-1,j} + (l_i-j+1) \times f_{i-1,j-1} \]

前一项表示不钦定 \(a_i\) 选更小的；后一项中 \(l_i\) 表示 \(a_i\) 在 \(b_i\) 中的排名（此处定义为最大的 \(b_j<a_i\) 的下标）。

然后考虑 \(g(x)\) 与 \(f_{i,j}\) 的关系，我们可以知道 \(g(x) = (n-j)! f_{n,j}\)，系数 \((n-j)!\) 来自剩余的的没有钦定的元素的自由组合。

套式子二，即可求出答案。

AT_abc423_f [ABC423F] Loud Cicada

题意：AtCoder 岛上有 \(n\) 种蝉。第 \(i\) 种蝉（\(1 \leq i \leq n\)）只有在年份是 \(a_i\) 的倍数时才会发生大爆发。在第 \(1\) 年到第 \(Y\) 年中，求恰好有 \(m\) 种蝉发生大爆发的年份有多少个。\(1 \le m \le n \le 20,1 \le a_i,Y \le 10^{18}\)

也就是说，求 \(\sum \limits_{i=1} ^ Y [\sum \limits _{j=1} ^n [a_i \mid i] =k]\)。

不好处理，考虑枚举集合，易得每个集合 \(S\) 的 \(\operatorname{lcm}\)，能够求出有 \(\left \lfloor \frac{Y}{\operatorname{lcm} \{S\}} \right \rfloor\) 年 \(S\) 内所有的蝉都大爆发，所有元素个数为 \(k\) 的集合的数值之和即至少 \(k\) 种蝉大爆发。

套用公式二即可。

题组（二）

这一部分主要是比较有意思毒瘤的组合与代数推导。

P6031 CF1278F Cards 加强版 （神题，*）

书接上回，我们已经求得，

\[E= \frac{1}{m^n}\sum _{j=0} ^k { k \brace j} j! \binom n j m^{n-j}\\ \]

这个式子即使使用多项式科技也只能做到 \(\Theta (k\log k)\)，而这个题目要求 \(O(k)\)。

我们回头来看这个式子。

\[m^n = \sum _{i=0} ^{\min \{m,n\}} {n \brace i} i! \binom m i \]

我们发现，这个式子在 \(m>n\) 时可以二项式反演！

二项式反演可得，

\[{n \brace m} =\frac{1}{m!} \sum _{i=0} ^m (-1) ^{m-i} \binom m i i^n \]

（这就是第二类斯特林的通项公式）

代入 \(E\) 可得

\[E = \frac{1}{m!} \sum _{j=0} ^k \sum _{i=0} ^j (-1) ^{j-i} \binom j i i^k \binom n j m^{n-j} \]

由恒等式 \(\binom n j \binom j i = \binom n i \binom {n-i} {j-i}\) 得

\[E=\frac{1}{m^n} \sum _{j=0}^k \sum_{i=0} ^j (-1)^{j-i} i^k \binom n i \binom {n-i} {j-i} m^{n-j} \]

和式变换：

\[E = \frac{1}{m^n} \sum_{i=0} ^k i^k \binom n i \sum_{j=i} ^{k} (-1) ^{j-i} \binom {n-i}{j-i} m^{n-j} \]

令 \(t=j-i,p=\frac{1}{m}\)：

\[\begin{align*} E &= \frac{1}{m^n} \sum_{i=0} ^k i^k \binom n i \sum_{t=0} ^{k-i} (-1) ^t \binom {n-i}{t} m^{n-i-t}\\&= \sum_{i=0} ^k i^k p^{i} \binom n i \sum_{t=0} ^{k-i} (-1) ^t \binom {n-i}{t} p^{t} \end{align*} \]

现在的问题在于后面那一项，似乎没有什么很好的办法。

设 \(S(i) = \sum \limits_{t=0} ^{k-i} \binom {n-i}{t} (-p)^{t}\)，考虑递推。

\[S(k) = 1,S(k-1) = 1 -p (n-k+1),\\ S(k-2)=1-p(n-k+2) + \frac{1}{2!} p^2 (n-k+2)^{\underline 2}\\ S(k-3)=1-p(n-k+3)+\frac{p^2}{2!}(n-k+3)^{\underline 2} + \frac{p^3}{3!} (n-k+3) ^{\underline 3} \]

看着这几个式子像是线性递推（关于 \(p\) 的次数逐渐上升），假设 \(S(i)= k S(i+1) +b\)，\(k\) 是关于 \(p\) 的式子。

考虑用帕斯卡等式 \(\binom n k = \binom {n-1}{k-1} + \binom {n-1}{k}\) 展开组合数。（注意组合数上面与 \(S(i+1)\) 相同）

\[\begin{align*} S(i) &= \sum_{t=0} ^{k-i} (-p)^t \Big [ \binom {n-i-1}{t} + \binom {n-i-1}{t-1} \Big ]\\ &= \sum_{t=0} ^{k-i} (-p)^t \binom {n-i-1}{t} + \sum_{t=1} ^{k-i} (-p)^t \binom {n-i-1}{t-1} \\ &={ \color{red} \sum _{t=0} ^ {k-i-1} (-p)^t \binom {n-i-1}{t}} + (-p) ^{k-i} \binom {n-i-1}{k-i} + \sum_{j=0} ^{k-i-1} (-p)^{j+1} \binom {n-i-1}{j}\\ &={\color{red} S(i+1)} + (-p)^{k-i}\binom {n-i-1}{k-i} + (-p) S(i+1) \\ &= (1-p) S(i+1) + (-p)^{k-i}\binom {n-i-1}{k-i} \end{align*} \]

现在我们来看 \(b\) 一项如何快速计算，

\[\binom {n-i-1} {k-i} = \frac{(n-i-1)^{\underline{k-i}}}{(k-i)!} = \frac{\frac{n^{\underline{1+k}}}{n^{\underline{i+1}}}}{(k-i)!} \]

现在我们能求 \(S(i)=(1-p)S(i+1) + b\) 了。

回到原式，

\[E= \sum_{i=0} ^k i^k p^{i} \binom n i S(i) \]

\(i^k\) 即 \(id_k(i)\) 为积性函数，欧拉筛即可。\(p^i\) 可以 naive 的预处理。欧拉筛放最前面，避免存质数额外占空间。\(\binom n i = \frac{n ^{\underline i}}{i!}\)

这样总共需要 fac（阶乘），ifac（阶乘逆元），n_u（\(n\) 的下降幂），in_u（\(n\) 的下降幂的逆元），id（\(id_k\)），pw（\(p^k\)）共 \(6\) 个 \(O(k)\) 的数组，总共约 \(230\) 兆，勉强够用。

可能需要注意常数优化。

注意：我们推的式子在 \(n \le k+2\) 的时候会由于下降幂出问题，所以这时直接按原式处理：

\[E=\sum_{i=0} ^ n \binom n i p^i (1-p)^{n-i} i^k \]

【mx 炼石 NOIP 模拟赛五-第一题】阿蛮

神仙题，除了打表没有任何思路。真的只有 NOIP T1 难度？我觉得比 CF1895F Fancy Arrays （*2600） 难得多。

题目链接

题面

在长安之中有一位绝世舞娘。这天她参加了一场选舞，相传优胜者会被招入皇宫。
有 \(n\) 位选手，舞娘是第 \(1\) 位选手。记第 \(i\) 位选手的观众有 \(a_i\) 个。
舞娘的总得分初始为 \(0\)。每个人都算自己的观众，所以初始所有 \(a_i\) 都为 \(1\)。
接下来 \(m\) 个时刻，第 \(i\) 个时刻会来一个人，并选择一位选手成为她的观众。 然而这里的人都很没有主见，具体来说，第 \(i\) 个人会从前 \(n+i-1\) 个观众中随机选择一名观众，和他选择同样的选手（即按 \(a_i\) 带权随机一名选手成为她的观众）。
然后总人数变为 \(n+i\)，舞娘获得 \(\max(0,a_1\times 2-(n+i))\) 的得分（累加入总得分中）。 兰兰非常向往这位舞娘。请你告兰兰，舞娘的期望总得分是多少。 由于大唐盛世国力昌盛，选舞会进行多次（本题多测）。
数据范围: 记 \(V=\sum n+\sum m\)。 对于 \(100\%\) 的数据，保证 \(1\leq T,n,m\leq 10^6,1\leq V\leq 10^7\)。

鬼知道这个兰兰是什么人。

这个题有一个 \(\max\)，导致期望的线性性不大好用了。考虑求概率分布。

设 \(f_{i,j}\) 为第 \(i\) 个人进来后舞娘的观众数为 \(j\) 的概率。

初始条件为 \(f_{0,1}=1\)。

简单地动态规划可以知道，

\[f_{i,j} = \frac{j-1}{n+i-1}f_{i-1,j-1} + \frac{n+i-1-j}{n+i-1} f_{i-1,j} \]

可以做到 \(O(n^2)\)。

鬼知道题解怎么直接注意到 \(f_{i,j} =\cdots\) 的。

我试了无数个方法，发现打表 - 找规律 - 数学归纳法最管用。

没啥思路，打个表试试（此处不要约分，可能掩盖了规律，横向为 \(j\)，纵向为 \(i\)）。

\(f_{i,j}\) \(j=1\) \(j=2\) \(j=3\) \(j=4\)
\(i=0\) \(1\) \(0\) \(0\) \(0\)
\(i=1\) \(\frac{n-1}{n}\) \(\frac{1}{n}\) \(0\) \(0\)
\(i=2\) \(\frac{(n-1)n}{n(n+1)}\) \(\frac{2(n-1)}{n(n+1)}\) \(\frac{2}{n(n+1)}\) \(0\)
\(i=3\) \(\frac{(n-1)n(n+1)}{n(n+1)(n+2)}\) \(\frac{3(n-1)n}{n(n+1)(n+2)}\) \(\frac{6(n-1)}{n(n+1)(n+2)}\) \(\frac{6}{n(n+1)(n+2)}\)

可以感受到一点上升幂的样子，分母比较规整，猜测为 \(n^{\overline{i}}\)，分子像 \((n-1)^{\overline{i+1-j}}\) 乘一个系数。

接着计算 \(f_{4,4}\) 可以发现这个系数为 \(24\)，\(i!\)。而系数从左向右递减，且 \(j=i\) 和 \(j=i+1\) 时系数相同，猜想为 \(j=i+1\) 时为 \(\frac{i!}{0!}\)，\(j=i\) 时为 \(\frac{i!}{1!}\)，\(j=1\) 时为 \(\frac{i!}{i!}\)，大胆猜测为 \(\frac{i!}{(i+1-j)!}\)。

所以我们大胆猜测：

\[\begin{align*} f_{i,j} &= \frac{i!(n-1)^{\overline{i+1-j}}}{(i+1-j)! n^{\overline{i}}}\\ &= \frac{(i+1)!(n+i-j-1)!(n-1)!}{(i-j+1)!(n-2)!(n+i-1)!} \end{align*} \]

考虑证明。假设当 \(i \in [0,i-1]\) 时已经成立，现证明 \(i\) 的时候也成立。

\[\begin{align*} \frac{j-1}{n+i-1}f_{i-1,j-1} &= \frac{(j-1)(i-1)!(n+i-j-1)!(n-1)!}{(n+i-1)(i-j+1)!(n-2)!(n+i-2)!} \\&= \frac{(j-1)(i-1)!(n+i-j-1)!(n-1)!}{(i-j+1)!(n-2)!(n+i-1)!} \end{align*} \]

\[\begin{align*} \frac{n+i-1-j}{n+i-1} f_{i-1,j} &= \frac{(n+i-1-j)(i-1)!(n+i-j-2)!(n-1)!}{(n+i-1)(i-j)!(n-2)!(n+i-2)!}\\ &= \frac{(i-1)!(n+i-j-1)!(n-1)!}{(i-j)!(n-2)!(n+i-1)!} \end{align*} \]

两式相加，提取公因式，可得

\[\begin{align*} f_{i,j}&= \frac{(i-1)!(n+i-j-1)!(n-1)!}{(i-j)!(n-2)!(n+i-1)!} \left ( \frac{j-1}{i-j+1} + 1 \right) \\&= \frac{(i-1)!(n+i-j-1)!(n-1)!}{(i-j)!(n-2)!(n+i-1)!} \frac{i}{i-j+1} \\&= \frac{(i+1)!(n+i-j-1)!(n-1)!}{(i-j+1)!(n-2)!(n+i-1)!} \end{align*} \]

而当 \(i=0\) 时显然成立。证毕！

你以为做完了，其实才刚刚开始。

上面那个式子太丑了，简单变个形

\[f_{i,j} =\frac{ \binom {n+i-j-1}{n-2} }{\binom {n+i-1}{n-1}} \]

我们现在要求

\[\begin{align*} E &= \sum _{i=1} ^m \sum _{j=1} ^{i+1} f_{i,j} \times \max(0,2j-n-i) \\ &= \sum _{i=1} ^m \sum _{j= \left \lceil \frac{n+i}{2} \right \rceil} ^{i+1} f_{i,j}(2j -n-i) \\ &=\sum _{i=1} ^m 2\Bigg (\sum _{j=\left \lceil \frac{n+i}{2} \right \rceil} ^{i+1} j f_{i,j}\Bigg ) - \sum _{i=1} ^m (n+i)\Bigg ( \sum _{j=\left \lceil \frac{n+i}{2} \right \rceil} ^{i+1} f_{i,j} \Bigg ) \end{align*} \]

先考虑 \(\sum \limits _{j=1} ^ {k} f_{i,j}\)。

\[\begin{align*} \sum _{j=1} ^ k f_{i,j} &= \sum _{j=1} ^k \frac{ \binom {n+i-j-1}{n-2} }{\binom {n+i-1}{n-1}} \\&= \frac{1}{\binom {n+i-1}{n-1}} \sum _{j=1} ^k \binom {n+i-j-1}{n-2} \end{align*} \]

由朱世杰恒等式，可得

\[\begin{align*} \sum _{j=1} ^ k f_{i,j} &= \frac{1}{\binom {n+i-1}{n-1}} \Big ( \tbinom {n+i-1}{n-1} - \tbinom {n+i-k-1}{n-1} \Big ) \\ &= 1- \frac{\binom {n+i-k-1}{n-1}}{\binom {n+i-1}{n-1}} \end{align*} \]

再来考虑 \(\sum \limits_{j=1} ^k j f_{i,j}\)

\[\begin{align*} \sum _{j=1}^k j f_{i,j} &= \sum_{j=1} ^k \frac{j \binom {n+i-j-1}{n-2} }{\binom {n+i-1}{n-1}} \\ &= \frac{1}{\binom {n+i-1}{n-1}} \sum _{j=1} ^k j \binom {n+i-j-1}{n-2} \end{align*} \]

令 \(l=n+i-j-1\)，得

\[\begin{align*} \sum _{j=1}^k j f_{i,j} &= \frac{1}{\binom {n+i-1}{n-1}} \sum _{l=n+i-k-1} ^{n+i-2} (n+i-1-l) \binom {l}{n-2} \\&=\frac{1}{\binom {n+i-1}{n-1}} \Big [(n+i)\sum_{l=n+i-k-1}^{n+i-2} \binom l{n-2} - \sum_{l=n+i-k-1} ^{n+i-2} (l+1) \binom {l}{n-2} \Big ] \end{align*} \]

前一项

\[\begin{align*} \sum_{l=n+i-k-1}^{n+i-2} \binom l{n-2} &= \sum _{l=0} ^ {n+i-2} \binom {l}{n-2} - \sum_{l=0} ^ {n+i-k-2} \binom {l}{n-2}\\ & = \binom {n+i-1} {n-1} - \binom {n+i-k-1}{n-1} \end{align*} \]

后一项

\[\begin{align*} \sum_{l=n+i-k-1} ^{n+i-2} (l+1) \binom {l}{n-2} &= (n-1) \sum _{l=n+i-k-1} ^ {n+i-2} \binom {l+1}{n-1} \\ &= (n-1) \sum _{l=n+i-k-1} ^ {n+i-1} \binom {l}{n-1} \\&= (n-1) \bigg ( \binom{n+i}{n} -\binom {n+i-k}{n} \bigg ) \end{align*} \]

几乎做完了，只剩下回代。这里就不写了，否则一行估计写不下。

生成函数入门

自从 FFT 被列为 10 级知识点后这个好像不大能考了。

一些前置知识

广义二项式系数

\[\binom x n = \frac{\prod _{i=0}^{n-1} (x-i)}{n!} ,\ x\in \R,n \in N \]

广义二项式定理

\[(x+y) ^ \alpha = \sum _{k=0} ^ \infty \binom \alpha k x^{\alpha-k} y^k \]

当右边的级数收敛是成立，在生成函数可以直接使用。

上指标反转

\[\binom {-n} m = (-1) ^m \binom {m+n-1} m \]

一些小练习：

\[\begin{align*} \frac{1}{1-x} &= (1-x) ^ {-1}\\& =\sum _{k=0} ^ \infty \binom {-1} k 1^{-1-k} (-x)^k \\& =\sum _{k=0} ^ \infty \binom {k} k (-1)^k(-x)^k \\& =\sum _{k=0} ^ \infty x^k \end{align*} \]

\[\begin{align*} \frac{1}{(1-x)^2} &= (1-x) ^ {-2}\\& =\sum _{k=0} ^ \infty \binom {-2} k 1 ^{-2-k} (-x)^k\\& =\sum _{k=0} ^ \infty \binom {k+1} k (-1)^k (-x)^k\\& =\sum _{k=0} ^ \infty (k+1) x^k \end{align*} \]

\[\begin{align*} \frac{1}{1+x} &= (1+x) ^{-1} \\&= \sum_{k=0} ^\infty \binom {-1}{k} x^k \\&=\sum _{k=0} ^ \infty (-x)^k \end{align*} \]

\[\begin{align*} \frac{1}{1-Cx} &= (1-Cx) ^{-1} \\&= \sum_{k=0} ^\infty \binom {-1}{k} x^k \\&=\sum _{k=0} ^ \infty (Cx)^k \end{align*} \]

\[\begin{align*} \frac{1}{(1-x) ^ t} &= (1-x) ^{-t}\\&= \sum _{k=0} ^ \infty \binom {-t}{k} (-x)^k\\&=\sum _{k=0} ^ \infty \binom {k+t-1}{k} x ^k \\&= \sum _{k=0} ^ \infty \frac{k^{\underline{t}}}{k!} x^k \end{align*} \]

\[\begin{align*} \frac{1}{1-x ^ t} &= (1-x)^{-t} \\ &= \sum _{k=0} ^ \infty \binom {-1}{k} (-x)^{tk} \\ &= \sum _{k=0} x^{tk} \end{align*} \]

一些 taylor 展开：

\[e^x = \sum _{n=0} ^\infty \frac{1}{n!} x^n \]

\[\ln (1-x) = - \sum _{n=0} ^ \infty \frac{1}{n} x^n \]

推论：

\[x e^x = \sum _{n=0} ^\infty \frac{n}{n!} x^n \]

\[e^{Cx} = \sum _{n=0} ^\infty \frac{C^n}{n!} x^n \]

单位根反演：

反演那没写，补在这里。

单位根反演与前几种反演有所不同，主要处理 \([n \mid k]\)。

前置知识：复数及其三角形式，单位根（\(x^n = 1\) 的所有复数根），等比数列求和。

单位根可以表示为单位圆上等分圆的若干点。

则这些根为 \(\omega _n^0,\omega _n^1, \cdots ,\omega _n ^{n-1}\)。

有两个显然的性质：

\[\omega _n ^ k = \omega _n ^{qn+k} \\ \omega _n ^ x \times \omega _n ^ y = \omega _n ^{x+y} \]

于是我们有这么一个式子

\[[n \mid m] = \frac{1}{n} \sum _{k=0} ^{n-1} \omega _n ^{km} \]

当 \(n \mid m\) 时，\(\omega _n ^ {km}= \omega _n ^ {kmt} = 1\)。

当 \(n \nmid m\) 时，\(\sum \limits _{i=0} ^{n-1} \omega _{n} ^{km} = \frac{1- \omega _n ^ {nm}}{1 - \omega _n^m}\)，分子为 \(0\) 而分母不为零，故整体等于 \(0\)。

证毕！

单位根反演：

若 \(F(x)\) 为一个 \(m\) 次多项式，即

\[F(x)=\sum _ {i=0} ^m f_{i} x ^ i \]

则

\[\sum _{k=0} ^m [n \mid k] f_{k} = \frac{1}{n} \sum_{i=0} ^{n-1} F(\omega _n ^i) \]

证明代入即可。读者自证不难。

\[\begin{align*} \sum _{k=0} ^m [n \mid k] f_{k} & = \sum _{k=0} ^ m \frac{1}{n} \sum _{i=0} ^ {n-1} \omega _n ^ {ik} f_k \\&=\frac{1}{n}\sum _{i=0} ^ {n-i }\sum _{k=0} ^ m f _k (\omega _{n} ^ i)^k \\&= \frac{1}{n}\sum _{i=0} ^{n-i} F(\omega _n ^ i) \end{align*} \]

在模意义下，原根具有于单位根类似的性质，可以完成单位根反演。此处不展开。例如，在模 \(998244353\) 下的最小原根 \(g\) 为 \(3\)，且 \(g^0,g^1,\dots,g^{P-2}\) 各不相同，\(g\) 相当于 \(\omega _{P-1}\)，显然满足我们要用的性质：

\[g ^ k \equiv g ^ {k+ q(P-1)},g ^x \times g^y = g^{x+y} \]

来看一道题：[LOJ 6485] LJJ 学二项式定理

求

\[ \bigg [ \sum _{i=0} ^n \Big ( \tbinom {n}{i} s^i a_{i \bmod 4} \Big ) \bigg ] \bmod 998244353 \]

以下省略 \(\bmod 998244353\)。

不妨写成

\[\sum _{j=0} ^ 3 a_j \sum _{i=0} ^n \binom n i s^i [4 \mid (i-j)] \]

后面有一个 \([4 \mid (i-j)]\) 不方便处理，我们可以考虑后一个和式的变形：

\[\sum _{i=0} ^n \binom n {i} s^{i} [4 \mid (i-j)] \]

将 \([n \mid m] = \frac{1}{n} \sum _{k=0} ^{n-1} \omega _n ^{km}\) 代入，得

\[\begin {aligned} &\quad \sum _{i=0} ^n \binom n {i} s^{i} [4 \mid (i-j)] \\ &= \sum _{i=0} ^n \binom n {i} s^{i} \frac{1}{4} \sum _{k=0} ^ 3 \omega _4 ^ {k(i-j)}\\&= \frac{1}{4} \sum _{k=0} ^ 3 \omega _ 4 ^{-kj} \sum _{i=0} ^n \binom n i (s \omega _4 ^k) ^i \\ &= \frac{1}{4} \sum _{k=0} ^ 3 \omega _ 4 ^{-kj} (s \omega _4 ^k +1) ^{n} \end{aligned} \]

一个问题：

\(\omega _4 \bmod 998244353\) 是多少？

已知模 \(998244353\) 下存在原根 \(g=3\)，\(998244352 = 2^{23} \times 7 \times 17\)，\(4 \mid 998244352\)，则 \(\omega _4 =g^\frac{998244352}{4} = 911660635\)。

为什么放在这里？

考虑这个式子（后面会知道，这和 EGF 有很大的关系）的封闭形式

\[1+ \frac{x ^m}{m!} +\frac{x ^{2m}} {(2m)!} + \cdots \]

即

\[G(x)=\sum _{i=0} ^ { \infty} \frac{x^i}{i!} [i \mid m ] \]

由 \(\sum _{k=0} ^m [n \mid k] f_{k} = \frac{1}{n} \sum_{i=0} ^{n-1} F(\omega _n ^i)\) 和 \(e^x = 1 + x+\frac{x^2}{2!}+\cdots\) 易得

\[G(x)= \frac{1}{m} \sum_{i=0} ^m e^ {\omega _m ^ i} \]

特例：

\[1+ \frac{x^2}{2!} + \frac{x^4}{4!} + \cdots = \frac{e ^ x + e ^{-x}}{2} \\ \]

推论：

\[ x + \frac{x^3}{3!} + \cdots = \frac{e ^ x - e ^{-x}}{2} \\ \]

普通生成函数（OGF）

对于数列 $A_1,A_2 ,\cdots $，定义其普通生成函数为

\[A(x)= \sum _{i\le 0} A_i x ^i \]

普通生成函数常用于处理“无标号”的问题。

P10780 BZOJ3028 食物

几个物品的 OGF 分别为：

  1. \(1+x^2+x^4+ \dots = \frac{1}{1-x^2}\)
  2. \(1+x\)
  3. \(1+x+x^2\)
  4. \(x+x^3+x^5 +\dots = \frac{x}{1-x^2}\)
  5. \(1+x^4+x^8 +\dots = \frac{1}{1-x^4}\)
  6. \(1+x+x^2+x^3\)
  7. \(1+x\)
  8. \(1+x^3+x^6 + \dots = \frac{1}{1-x^3}\)

全部乘起来

这绝对是我写过的最乱的式子

\[\begin{align*} G(x)&=\frac{1}{(1-x)(x+1)} (x+1) (1+x+x^2)\frac{x}{(1-x)(x+1)}\frac{1}{(1-x)(1+x+x^2+x^3)} (1+x+x^2+x^3) (x+1)\frac{1}{(1-x)(1+x+x^2)}\\ &=\frac{1}{(1-x)} \frac{x}{(1-x)}\frac{1}{(1-x)} \frac{1}{(1-x)}\\ &=\frac{x}{(x-1)^4} \\ &=x(x-1)^{-4} = x \sum _{k=0} ^ \infty \binom {-4}{k} (-1)^{-4-k} x^k \\ &= x \sum_{k=0} ^ \infty (-1)^k \binom {k+3}{k} (-1)^k x^k\\ &= x\sum _{k=0} ^{\infty} \frac{(k+3)(k+2)(k+1)}{6} x^k \\ &= \sum _{k=1} ^{\infty} \frac{(k+2)(k+1)k}{6} x^k \end{align*} \]

\[[x^n] G(x) = \frac{(k+2)(k+1)k}{6} \]

指数生成函数

对于数列 $A_1,A_2 ,\cdots $，定义其指数生成函数为

指数生成函数常用于处理“有标号”的问题

P2012 拯救世界2

考虑每种基因的 EGF：

  • A,T,C,G： \(1 +x+\frac{x^2}{2!} + \dots = e^x\)
  • 乾、坎、艮、震：\(x+\frac{x^3}{3!} + \frac{x^5}{5!} = \frac{e^x+e^{-x}}2\)
  • 坤、兑、离、巽：\(1+\frac{x^2}{2!} + \frac{x^4}{4!}=\frac{e^x-e^{-x}}2\)

总生成函数：

\[\begin{align*} G(x)&= e^{4x} \times \left (\frac{e^x+e^{-x}}{2}\right )^4 \times \left (\frac{e^x-e^{-x}}{2}\right )^4\\&=e ^{4x} \times \left (\frac{e^{2x}-e^{-2x}}{4}\right )^4 \\&= \left( \frac{e ^ {3x} - e ^{-x}}{4} \right) ^4\\&= \frac{1}{256} (e^{6x}+ e ^{-2x} - 2 e ^ {2x})^2\\&=\frac{1}{256} (e^{12x}- 4e ^{8x} + 6 e ^{4x}-4+e ^{-4x}) \end{align*} \]

答案为

\[\begin{align*} n! [x^n]G(x) &= \frac{n!}{256} (\frac{12^n}{n!}- \frac{4 \times 8^n}{n!}+\frac{6 \times 4^n}{n!} + \frac{(-4)^{n}}{n!}) \\ &= \frac{12^n- 4 \times 8^n +6 \times 4^n +(-4)^{n}}{256} \end{align*} \]

注意到 \(256 = 2 ^8\) 在模 \(10^9\) 下逆元不存在，而分子在 \(n \ge 4\) 是每一项可以整除 \(2^8\)，故 \(n\) 较小时暴力算，\(n\) 较大时取模。

生成函数剩下的内容只能咕到省选之后了。

trick - 计数转期望

HDU - 5396 Expression

期望转概率，可以算套路题。

显然，一共有 \((n-1)!\) 种情况。

这个形式很难不想区间 dp。

设 \(f_{l,r}\) 为 \(a[l,r]\) 最后的结果的期望，边界条件 \(f_{i,i}= a_i\)。

转移可以考虑最后一个合并的符号，可以得到

\[f_{i,j} \gets \frac{1}{j-i} \sum _{k=i} ^{j-1} f_{i,k} \oplus _k f_{k+1,j} \]

其中，\(\oplus_i\) 表示执行该操作。

结果为 $ (n-1)! f_{1,n} $

AT_agc030_d [AGC030D] Inversion Sum *

妙妙题。

考虑转成期望。每个操作以 \(\frac 1 2\) 的概率执行，求期望逆序对数。

设 \(f_{i,j}\) 为当前状态下，\(A_i>A_j\) 的概率，每次会更改的状态只有与 \(f_{x/y,*}\) 和 \(f_{*,x/y}\) 共 \(O(n)\) 个。

转移可得

  1. \(f_{x,y} ^\prime = f_{y,x} ^\prime = \frac{f_{x,y}+f_{y,x}}{2}\)
  2. \(f_{x,u} ^\prime = \frac{f_{x,u}+f_{y,u}}{2}\)
  3. \(f_{y,u} ^\prime = \frac{f_{x,u}+f_{y,u}}{2}\)
  4. \(f_{u,x} ^\prime = \frac{f_{u,x}+f_{u,y}}{2}\)
  5. \(f_{u,y} ^\prime = \frac{f_{u,x}+f_{u,y}}{2}\)

有了概率分布，求期望也是容易的，再乘以 \(2^q\) 即可。

题组 3

最近打的比赛的题。

ABC450F Strongly Connected 2

rating 掉大了。

看着这个题，第一反应是大概率要线段树优化 DP。

设 \(f_{i}\) 为最大的连通分量为 \(i\) 的方案数。则答案最后为 \(f_n\)。初始时 \(f_1=1\)。

考虑加入一条边 \(u \to v\) 会有什么影响。

显然的一点是对于 \(i \lt u\) 和 \(i \gt v\)，加入这条边与否不会影响最大为 \(i\) 的联通分量，故 \(f^\prime_{i} \gets f_i \times 2\)。

现在只需要考虑 \(u \le i \le v\)。原来最大连通分量为 \(j,u\le j \le v\) 的连通分量在加入这条边大小后会变成 \(v\)，而不加入这条边的话保持不变。故 \(f ^\prime_v \gets f_v + \sum \limits_{i=u} ^v f_i\)，\(f ^\prime _j \gets f_j (u \le j \lt v)\)。

但是我们会发现这会有问题。考虑一次一共 \(3\) 个点添加 \(2 \to 3\) 和 \(1 \to 2\) 两条边。第一次 \(2 \to 3\) 会“虚空转移”，即加入 \(2 \to 3\) 的时候连 \(2\) 都到不了。这个问题也是容易解决的，我们只需要对 \(u \to v\) 按 \(u\) 升序排序即可。

一点教训

赛时我设 \(f_i\) 表示 \([1,i]\) 在同一个连通分量的方案数，导致转移非常困难。所以当面临转移困难时应该考虑改变状态定义或者加一维。

ABC450G Random Subtraction

注意到，\(x= \sum \limits_{i=0} ^n c_i A_i,c_i \in \{-1,1\}\)。

所以

\[\begin{align*} x^2 &= \left (\sum_{i=1} ^n c_i A_i \right) ^2 \\&= \sum _{i=1} ^n (c_iA_i) ^2 + 2\sum _{i=1} ^n \sum _{j=i+1} ^n c_i c_j A_i A_j \\&= \sum _{i=1} ^ n A_i^2 + 2\sum _{i=1} ^n \sum _{j=i+1} ^n c_i c_j A_i A_j \end{align*} \]

那么

\[\begin{align*} E [x^2] &= \sum _{i=1} ^n A_i^2 + 2 E[\sum _{1 \le i \lt j \le n} c_ic_jA_iA_j] \end{align*} \]

而 \(\forall 1\le i,j,k,l \le n\)，易知 \(E[c_ic_j]=E[c_kc_l]\)，（因为题目的选择方式与初始位置无关的），不妨设这个只与 \(n\) 有关的值为 \(K_n\)。

则

\[\begin{align*} E[x^2] &= \sum _{i=1} ^n A_i ^2 + 2 K_n \sum _{1 \le i \lt j \le n} A_i A_j \end{align*} \]

其他项都是容易的，关键在于如何且 \(K_n\)。

显然 \(K_1 =0,K_2=-1\)。手玩以下可以发现 \(K_3=-\frac{1}{3}\)。

选择 \(A_i-A_j\) 后会将它们视为一个整体 \(X\)。减 \(X\) 相当于将两个数的 \(c\) 全部取反。这样，无论如何 \(c_i \times c_j = -1\)。

不妨假设我们选择了 \(A_1,A_2\)，这样发生的概率为 \(\frac{n(n-1)}{2}\)。故 \(c_1c_2=-1,c_1c_i + c_2 c_i=0\)。而剩余的 \(n-2\) 个元素会与合并的新元素一起继续操作 \(E[c_i c_j]=K_{n-1}\)。所以 \(K_n = \frac{-1+\frac{(n-2)(n-3)}{2}K_{n-1}}{\frac{n(n-1)}{2}} = \frac{-2+(n-2)(n-3)K_{n-1}}{n(n-1)}\)。

一下午困得很，可能写错了。

后记

参考资料：

posted @ 2026-02-24 11:42  MZMTab  阅读(93)  评论(0)    收藏  举报