组合数学学习笔记（二）：鸽巢原理、容斥及反演
orange_new
·
2024-07-04 10:02:48
·
算法·理论
鸽巢原理
将 \displaystyle\sum_{i = 1}^n p_i - n + 1 个物品放入 n 个盒子，一定存在一个盒子 i ，使得第 i 个盒子至少装了 p_i 个物品。
证明：考虑反证法。
假设每个盒子 i 都装了小于 p_i 个物品，那么物品数量最大当且仅当每个盒子 i 都装了 p_i - 1 个物品，那么物品数就是 (p_1 - 1) + (p_2 - 1) + (p_3 - 1) + \dots + (p_n - 1) = \displaystyle\sum_{i = 1}^n p_i - n ，此时物品数小于物品总数，矛盾，因此 一定存在一个盒子 i ，使得第 i 个盒子至少装了 p_i 个物品。
推论： 如果把 n(r - 1) + 1 个物品放入 n 个盒子中，那么一定有一个盒子中至少装了 r 个物品。
证明：把所有的 p_i 取成一样就可以了。
练习一
有十个数 a_1, a_2, \dots a_{10} 满足 \forall_{1 \leq i \leq 10}{1 \leq a_i \leq 60} ，证明能够从 a_i 中挑出两个交为空的子集，使得它们的和相等。
证明：首先，由于 1 \leq a_i \leq 60 ，那么这个子集的和就有可能是 0 到 600 这 601 个数中的一个，而可能的子集数为 2^{10} = 1024 ，根据鸽巢原理，一定有两个子集的和相等。
如果这两个集合没有交集，那么已经满足题目的要求；如果这两个集合有交集，那就将这两个集合同时减掉交集，此时两个集合的和依然相等，而且仍然为全集的子集，原命题证明成立。
练习二
证明一张有超过 1 个点的简单无向图必定有两点度数相等。
解：考虑反证法。
一个 n 个点的简单无向图，每个点的度数是 0 到 n - 1 中的一个，假设这 n 个点的度数恰好是 0 到 n - 1 各一个，但由于度数为 n - 1 的点一定向其它 n - 1 个点个连了一条边，因此不存在度数为 0 的点，矛盾。于是度数 0 和 n - 1 不能同时出现，因此度数的选择只有 n - 1 种。
根据鸽巢原理，这 n 个点中一定有两个点度数相等，原命题证明成立。
练习三
前置知识：线性代数学习笔记（一）（2024.7.24）
证明能从任意 11 个实数中挑选出 4 个数 a, b, c, d 满足：
(ac + bd)^2 \geq \displaystyle\frac 12(a^2 + b^2)(c^2 + d^2)
证明：考虑两个向量 u = \begin{bmatrix} a \\ b \end{bmatrix}, v = \begin{bmatrix} c \\ d \end{bmatrix} ，它们的点积为 \begin{bmatrix} a \\ b \end{bmatrix} \cdot \begin{bmatrix} c \\ d \end{bmatrix} = ac + bd ，那么右边又可以改写成 (u \cdot v)^2 这是左边的几何含义。
这两个向量的模长分别是 \sqrt{a^2 + b^2} 和 \sqrt{c^2 + b^2} ，那么右边又可以改写成 \displaystyle\frac 12 |u|^2|v|^2 ，这是右边的几何含义。
考虑到点积的几何意义是将一个向量 u 投影到另一个向量 v 上，再用投影长度乘以 v 的模长，设这两个向量的夹角为 \theta ， 那么点积可以表示成 |u||v| \cos \theta ，那么左边又可以写成 |u|^2|v|^2 \cos^2 \theta 。
这时原先的不等式变成了 |u|^2|v|^2 \cos^2 \theta \geq \displaystyle\frac 12 |u|^2|v|^2 ，消去相同的项，可以得到 \cos^2 \theta \geq \displaystyle\frac 12 ，即 \cos \theta \geq \displaystyle\frac{\sqrt 2}{2} 或 \cos \theta \leq -\displaystyle\frac{\sqrt 2}{2} ，即 \theta \in [0, \displaystyle\frac{\pi}{4}] \cup [\frac{3 \pi}{4}, \pi] 。
现在考虑将平面每旋转 \displaystyle\frac{\pi}{4} 划分一次，将平面划分成 8 个部分，由于有 11 个数字，根据鸽巢原理，一定有 2 个向量位于同一个部分内，那 \theta 一定满足要求，原命题证明成立。
练习四
证明由任意 n^2 + 1 个互不相同的实数构成的序列 a_1, a_2, \dots, a_{n^2 + 1} ，要么含有长度为 n + 1 的递增子序列，要么含有长度为 n + 1 的递减子序列。
证明：先假设原序列不存在长度为 n + 1 的递增子序列，来证明原序列存在长度为 n + 1 的递减子序列。
设 m_k 表示从 a_k 开始的最长递增子序列的长度，那么根据假设，\forall k \in [1, n^2 + 1], m_k \leq n ，又因为 m_k \geq 1 ，所以 m_1, m_2, \dots, m_{n^2 + 1} 为 1 到 n 之间的整数，根据鸽巢原理，这 n^2 + 1 个数中必然有 n + 1 个是相同的数。
假设相同的 m 分别是 m_{k_1} = m_{k_2} = \dots = m_{k_{n + 1}} ，其中 1 \leq k_1 < k_2 < \dots < k_{n + 1} \leq n^2 + 1 ，再假设 \exists i \in [1, n], a_{k_i} < a_{k_{i + 1}} ，由于 k_i < k_{i + 1} ，那么可以在 a_{k_{i + 1}} 的最长递增子序列前面加上 a_{k_i} 使得 m_{k_i} > m_{k_{i + 1}} ，这与假设矛盾，因此不存在 a_{k_i} < a_{k_{i + 1}} ，于是 a_{k_1} > a_{k_2} > \dots > a_{k_{n + 1}} ，此时这是一个长度为 n + 1 的递减子序列，原命题证明成立。
容斥原理
其实这个东西我们在小学时就学过了，比如题目，其实这就是容斥原理。一般，如果我们要不重不漏地统计至少具有一种特性的某些物品的系数，就需要考虑如何减掉重复的，如何加上漏掉的，这时就需要用容斥原理来统计。用计算式来表达就是：
|\displaystyle\bigcup_{i = 1}^n A_i| = \sum_{j = 1}^n (-1)^{j - 1} \sum_{1 \leq k_1 < k_2 < k_3 < \dots < k_j \leq n} |\bigcap_{l = 1}^j A_{k_l}|
用人话说就是如果你想求出一些集合的并集的大小，你只需要加上这些集合的大小，减掉任意两个集合的交集，加上任意 3 个集合的交集，重复这种奇数个集合就加，偶数个集合就减的方式，就可以得到，下面来证明为什么。
定理2.1
设 P_1, P_2, \dots, P_m 为研究对象的 m 种性质，A_m 为具有 P_m 性质的对象所构成的集合，A_i \bigcap A_j \bigcap A_k 表示同时具有 P_i, P_j, P_k 性质的对象所具有的，\overline{A_1} \bigcap \overline{A_j} \bigcap \dots \bigcap \overline{A_m} ，表示不具有任何性质的对象所构成的集合。
那么不具有性质 P_1, P_2, \dots, P_m 的对象个数由下面的交错表达式给出 |\overline{A_i} \bigcap \overline{A_j} \bigcap \dots \bigcap \overline{A_m}| = |S| - \displaystyle\sum|A_i| + \sum|A_i \bigcap A_j| - \sum|A_i \bigcap A_j \bigcap A_k| + \dots + (-1)^m|\sum A_i \bigcap A_j \bigcap \dots \bigcap A_m| 。
证明：先考虑只有两个性质的情况，那么 |\overline{A_1} \bigcap \overline{A_2}| = |S| - |A_1| - |A_2| + |A_1 \bigcap A_2| ，现在我们只需要证明，一个既不具有 P_1 性质，也不具有 P_2 性质的元素对于右边式子的贡献为 1 ，而具有 P_1 或 P_2 性质的元素对于右边式子的贡献为 0 。
假设元素 x 既不具有 P_1 性质，也不具有 P_2 性质，那么它只被包含在 S 中，对于右边式子的贡献为 1 - 0 - 0 + 0 = 1 。
假设元素 x 只具有 P_1 性质，那么它被包含在 S, A_1 中，对于右边式子的贡献为 1 - 1 - 0 + 0 = 0 。
假设元素 x 只具有 P_2 性质，那么它被包含在 S, A_2 中，对于右边式子的贡献为 1 - 0 - 1 + 0 = 0 。
假设元素 x 既具有 P_1 性质，也具有 P_2 性质，那么它被包含在 S, A_1, A_2, A_1 \bigcap A_2 中，对于右边式子的贡献为 1 - 1 - 1 + 1 = 0 。
那么右边等式计算出的结果就是既不具有性质 P_1 ，也不具有性质 P_2 的元素的个数。
现在考虑拓展到一般，假设元素 x 不具有任意一个性质，那么他对右边的贡献就是 1 - 0 + 0 - 0 + \dots + (-1)^m0 = 1 。
考虑一个具有 n(n \leq m) 个性质的元素 y ，我们可以从这 n 个性质中任意选出 k 个来，那么 A_1 \bigcap A_2 \bigcap \dots \bigcap A_k 这个集合中，而一共有 \displaystyle\binom{n}{k} 个包含 y 且大小为 k 的集合你，那么答案就是 \displaystyle\sum_{k = 1}^m (-1)^k \binom{n}{k} = \sum_{k = 0}^n (-1)^k \binom{n}{k} ，套用二项式定理，这个式子 = [1 + (-1)]^n = 0 ，于是 y 对右边式子的贡献为 0 。
现在，只有不具有任何性质的元素对等式右边有贡献，定理 2.1 证明成立。
感性理解就是减多了就加，加多了就减。
定理2.2（容斥原理）
|A_1 \bigcup A_2 \bigcup \dots \bigcup A_m| = \displaystyle\sum|A_i| - \sum|A_i \bigcap A_j| + \sum|A_i \bigcap A_j \bigcap A_k| - \dots - (-1)^{m + 1}|\sum A_i \bigcap A_j \bigcap \dots \bigcap A_m|
证明：将定理1.1两边同时用 |S| 减即可证明。
简单容斥
P1450 [HAOI2008] 硬币购物
P10681 [COTS 2024] 奇偶矩阵 Tablica
容斥系数
例题三
如何现在有一个序列 a_n ，0 \leq a_n \leq m ，请问有多少个序列满足：不存在两个连续的 0 ？
例题四
问对于所有长为 n 的排列，有多少排列存在一个连续上升段 \geq k 。对所有 k 回答，对大质数取模。
AT_agc058_d [AGC058D] Yet Another ABC String
反射容斥
P3266 [JLOI2015] 骗我呢
CF GYM 104053J Math Exam
反演
基本概念
广义的反演，就是两个函数之间互相推倒的关系，比如 f(x) = xg(x) ，那么 g(x) = \displaystyle\frac{f(x)}{x} ，放到离散意义下，就可以表示两个数列之间之间互相推导的关系，比如 F(n) = \displaystyle\sum_{i = 1}^n G(i) （前缀和），那么 G(n) = F(n) - F(n - 1) （差分），这就是信息学中常见的反演。
我们可以用矩阵来表示一对反演关系。此我们把 G(1) \sim G(n) 看成一个向量 \boldsymbol g ，把 F(1) \sim F(n) 看成一个向量 \boldsymbol f ,那么 F(n) 的计算式，就可以看成是一个矩阵 A 第 n 行的每一个值分别乘以 \boldsymbol g 每一列的值，因此可以把反演关系写成记作 \boldsymbol f = A \times \boldsymbol g 。
此时，如果我们想要用 F(n) 来推导 G(n) ，只需要在等式两边同时乘以逆矩阵，因此 A^{-1} \times \boldsymbol f = \boldsymbol g 。
拿我们刚才举的前缀和与差分的例子来说。前缀和的矩阵 A 的第 i 行在 1 \sim i 会全是 1 ，而差分的矩阵 B 的第 i 行只会在第 i 列为 1 ，在第 i - 1 列为 -1 ，其它列全是 0 ，我们对这两个矩阵做矩阵乘法，可以得到：
C_{i, j} = \displaystyle\sum_{k = 0}^n A_{i, k} \times B_{k, j} = \sum_{k = 0}^n [j \leq i] - [j + 1 \leq i] = [i = j]
可以发现这是一个单位矩阵，因此两个互为反演的关系矩阵互逆 。
性质
一对互逆的矩阵转置之后仍然互逆。
一对互逆的矩阵分别数乘 c （c \neq 0 ) 后仍然互逆。
等式两边同时乘以 $(-1)^{j - i}$ 即可证明。
复合
如果同时存在两组反演：
\begin{aligned}
F(n) = \displaystyle\sum_{i = 1}^n A_{1_{n, i}} G(i) &\iff G(n) = \displaystyle\sum_{i = 1}^n B_{1_{n, i}} F(i)\\
F(n) = \displaystyle\sum_{i = 1}^n A_{2_{n, i}} G(i) &\iff G(n) = \displaystyle\sum_{i = 1}^n B_{2_{n, i}} F(i)
\end{aligned}
此时如果我们可以将 F 和 G 的定义域扩展到二维，那么有如下结论：
F(n, m) = \displaystyle\sum_{i = 0}^n \displaystyle\sum_{j = 0}^m A_{1_{n, i}} A_{2_{m, j}} G(i, j) \iff G(n, n) = \displaystyle\sum_{i = 0}^n \displaystyle\sum_{j = 0}^m B_{1_{n, i}} B_{2_{m, j}} G(i, j)
证明：我们构造一个四维的矩阵 A_{(n, m), (i, j)} = A_{1_{n, i}} A_{2_{m, j}} ，B 类似。
大力推式子：
\begin{aligned}
C_{n, m} &= \displaystyle\sum_{i = 0}^n \sum_{j = 0}^m A_{(n, m), (i, j)} B_{(i, j), (n, m)} \\&= \sum_{i = 0}^n \sum_{j = 0}^m A_{1_{n, i}} A_{2_{m, j}} B_{1_{i, n}} B_{2_{j, m}} \\&= \sum_{i = 0}^n A_{1_{n, i}} B_{1_{i, n}} \sum_{j = 0}^m A_{2_{m, j}} B_{2_{j, m}} \\&= [n = m]
\end{aligned}
这个证明可以很容易地推广到更多维。
种类
信息学竞赛中常见的反演有以下几种：
二项式反演：与容斥原理有关，一般解决“恰好”与“至多（少）”、“给定”与“任意”之间的转换关系。该反演将在本博客中讲解；
Min-Max 反演：与容斥原理有关，将 \min 用 \max 表示，或将 \max 用 \min 表示，在某些题中可以改变枚举顺序或枚举类型。该反演将在本博客中讲解；
子集反演：与高维前缀和有关系，一般结合快速莫比乌斯变换或快速沃尔什变换可以处理高位空间中特殊的数点问题。该反演将在本博客中讲解；
单位根反演：与多项式有关，用 DFT 求出多项式单位根处的取值后，用单位根反演重新插值出原函数。该反演将在多项式学习笔记（一）：多项式基础知识、快速傅里叶变换中讲解；
莫比乌斯反演：与数论有关，一般用于含有 [a = b] 的式子的简化。该反演将在数论学习笔记（二）：数论函数中讲解；
斯特林反演：与组合数学有关，由于第二类斯特林数是好求的，运用斯特林反演之后可以计算出第一类斯特林数，在上升幂、普通幂、下降幂之间的转化有用处。该反演将在组合数学学习笔记（四）：特殊的数中讲解；
二项式反演
基本形式
先来看一下最基本的式子：
F(n) = \displaystyle\sum_{i = m}^n \binom ni G(i) \iff G(n) = \sum_{i = m}^n(-1)^{n - i}\binom ni G(i)
这个式子有一个等价形式，就是
F(n) = \displaystyle\sum_{i = m}^n (-1)^i \binom ni G(i) \iff G(n) = \sum_{i = m}^n (-1)^i \binom ni G(i)
这个式子可以说是非常的对称，根据反演可以看作矩阵乘法，那么该矩阵 A \times A = I 。
我们可以先从线性代数的角度来证明一下：
证：
或者可以最暴力地带入证明：
证：F(n) = \displaystyle\sum_{i = m}^n \binom ni \sum_{j = m}^i (-1)^{i - j} \binom ij F(j)
考虑改变求和顺序，那么原式
= \displaystyle\sum_{j = m}^n F(j) \displaystyle\sum_{i = j}^n \binom ni \binom ij (-1)^{i - j}
套用三项式系数恒等式，那么原式
= \displaystyle\sum_{j = m}^n F(j) \displaystyle\sum_{i = j}^n \binom nj \binom{n - j}{i - j} (-1)^{i - j}
再次调整计算顺序，那么原式
= \displaystyle\sum_{j = m}^n \binom nj F(j) \displaystyle\sum_{i = j}^n \binom{n - j}{i - j} (-1)^{i - j}
将枚举 i 替换为枚举 i - j ，那么原式
= \displaystyle\sum_{j = m}^n \binom nj F(j) \sum_{i = 0}^{n - j} \binom{n - j}{i} (-1)^i
发现内层求和是一个二项式定理的形式，可以写成 [1 + (-1)]^{n - j} 形式，而这个式子只有在 n - j = 0 时才有值 1 ，于是原式最终写成
\displaystyle\sum_{j = m}^n \binom nj F(j) [n = j] = F(n)
F(n)=\sum\limits_{i=m}^n\dbinom im G(i)
\\
G(n)=\sum\limits_{i=m}^n(-1)^{i-m}\dbinom im F(i)
第二种形式证明类似。
P10596 BZOJ2839 集合计数
有 n 个元素，问有多少种选择若干个子集的方案，使得选出的子集的交集大小恰好为 k 。
0 < k \leq n \leq 10^6
解：直接钦定 i 个的方案数是 F(i)=\dbinom ni(2^{2^{n-i}}-1) ，设答案为 G(i) ，观察到
F(i)=\sum\limits_{j=i}^{n}{\dbinom {j}{i} G(j)}
那么反演即可得到：
G(k)=\sum\limits_{i=k}^n\dbinom ik F(i)
=\sum\limits_{i=k}^n(-1)^{i - k}\dbinom ik \dbinom ni (2^{2^{n-i}}-1)
这样之后直接做就行了。
P4859 已经没有什么好害怕的了
一句话题意：有两个序列 {a_i},{b_i} 保证所有元素互不相同。你需要重排 b 序列，使得恰好有 k 个 i 满足 a_i>b_i 。
0<k\leq n\leq2000
解：先将 a 序列排序。
考虑设 dp_{i,j} 表示考虑了前 i 对数，恰有 j 对 a_x>b_x ，发现完全没法转移（
主要是你配大的和配小的总有一个转不了，所以你考虑只算其中一个，也就是钦定有 j 对数满足 a_x>b_x ，发现这样就可以转了。
dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times(cnt(a_i)-j+1)
然后设 $f(i)$ 表示钦定了 $i$ 对的方案数，$g(i)$ 表示恰好 $i$ 对的方案数。观察可得：
$(n-i)!dp_{n,i}=f(i)=\sum\limits_{j=i}^n\dbinom ji g(j)
g(k)=\sum\limits_{i=k} ^n{(-1)^{i-k}\dbinom ik(n-i)!dp_{n,i}}
就可以直接做了。
CF997C Sky Full of Stars
一句话题意：有一个 n\times n 的矩阵，将其三染色，使得至少有一行或者一列同色，问方案数。
n\leq10^6
解：直接钦定 i 行 j 列同色：
F(i,0)=3^{(n-i)n+i}\dbinom ni
F(0,j)=3^{(n-j)n+j}\dbinom nj
F(i,j)=3^{(n-i)(n-j)+1}\dbinom ni\dbinom nj
考虑恰好 i 行 j 列同色：
G(0,0)=3^{n^2}+\sum\limits_{i=1}^n(-1)^{n-i}\dbinom ni(F(0,i)+F(i,0))+\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^{2n-i-j}\dbinom i0\dbinom j0 F(i,j)
后面那坨东西带进去：
\sum\limits_{i=1}^n\sum\limits_{j=1}^n3^{n^2-ni-nj+ij+1}(-1)^{2n-i-j}\dbinom ni\dbinom nj
=3^{n^2+1}\sum\limits_{i=1}^n{3^{-ni}(-1)^{n-i}\dbinom ni\sum\limits_{j=1}^n{(3^{n-i})^{j}(-1)^{n-j}\dbinom nj}}
=3^{n^2+1}\sum\limits_{i=1}^{n}{3^{-ni}(-1)^{n-i}((3^{n-i}-1)^n-(-1)^n)}
然后就做完了。
min / max反演（容斥）
\max{S}=\sum\limits_{T\subseteq S}{(-1)^{|T|-1}\min{T}}
\\
\max_{k_{th}}{S}=\sum_{T\subseteq S}{(-1)^{|T|-k}\binom{|T|-1}{k-1}\min{T}}
证：$\max\limits_{k_{th}}{S}=\sum\limits_{T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}\min T}
=\sum\limits_{x\in S}x\sum\limits_{x\in T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}[\min{T}=x]}
令 f(x) 表示 S 中大于 x 的元素构成的集合。
=\sum\limits_{x\in S}{x}\sum\limits_{x\in T\subseteq f(x)}{(-1)^{|T|-k}\dbinom{|T|-1}{k-1}}
枚举 |T| :
=\sum\limits_{x\in S}{x\sum\limits_{l = 1}^{|f(x)|}{(-1)^{l-k}\dbinom{|f(x)|-1}{l-1}\dbinom{l-1}{k-1}}}
=\sum\limits_{x\in S}{x\sum\limits_{l=1}^{|f(x)|}{(-1)^{l-k}\dbinom {|f(x)|-1}{k-1}\dbinom{|f(x)|-k}{l-k}}}
=\sum\limits_{x\in S}{x\dbinom {|f(x)|-1}{k-1}\sum\limits_{l=1} ^{|f(x)|}{(-1)^{l-k}\dbinom {|f(x)|-k}{l-k}}}
易知 |f(x)|< k 时无贡献。
=\sum\limits_{x\in S}{x\dbinom {|f(x)|-1}{k-1}\sum\limits_{l=0}^{|f(x)|-k}(-1)^l\dbinom{|f(x)|-k}{l}}
=\sum\limits_{x\in S}{x\dbinom {|f(x)|-1}{k-1}[|f(x)|=k]}
=\max\limits_{k_{th}}{S}
练习
给定三个序列 a_i,b_i,c_i ，求
\sum\limits_{1\leq i<j\leq n}{\max{a_i+a_j,b_i+b_j,c_i+c_j}-\min{a_i+a_j,b_i+b_j,c_i+c_j}}
n\leq2\times10^5
解：暴力拆开那个 max :
\max{a_i+a_j,b_i+b_j,c_i+c_j}
=\min{a_i+a_j}+\min{b_i+b_j}+\min{c_i+c_j}-\min{a_i+a_j,b_i+b_j}\\-\min{a_i+a_j,c_i+c_j}-\min{b_i+b_j,c_i+c_j}+\\\min{a_i+a_j,b_i+b_j,c_i+c_j}
抵消掉最后那一项，剩下的项中，只有一个的是平凡的，有两个的可以二维偏序，总复杂度就是 O(n\log{n}) 。
例题三
一句话题意：给 n 个元素，每次会随机选择一个，有 p_i 的概率选择第 i 个，问第一次所有元素都被选择过的期望时间。
1\leq n\leq20
解：因为 min/max 容斥都是线性运算，且期望具有线性性，所以可以直接套上期望：
E(\max{S})=\sum\limits_{T\subseteq S}{(-1) ^{|T|-1}E(\min{T})}
E(\min{T})$ 的含义实际上就是第一次选到 $T$ 中元素的期望时间，可以把 $T$ 和 $T$ 的补集看做两个整体，那么一次选中的概率就是 $\frac 1{\sum\limits_{x\in T}{p_x}}$，期望时间就是其倒数 $\sum\limits_{x\in T}{p_x}
然后直接带进式子里计算即可，O(n2^n) 。
例题四
一句话题意：给 n 个元素，每次会随机选择一个，有 \frac M {p_i} 的概率选择第 i 个，问第一次有 k 元素被选择过的期望时间。
解：相当于求期望出现时间第 $n-k$ 大，令 $k\leftarrow n-k$，一样的期望式子列出来：
$E(\max\limits_{k_{th}}S)=\sum\limits_{T\subseteq S}{(-1)^{|T|-1}\dbinom {|T|-1}{k-1}\frac{m}{\sum\limits_{x\in T}p_x}}
直接求肯定 G。因为 M\leq10^4 ，所以考虑计算每一种 \sum\limits_{x\in T}{p_x} 作为分母的项的系数之和，再算答案。
考虑设 dp_{i,j} 表示前 i 个，分母和为 j 的项的系数和。
不选很好转移，选的话中间那坨组合数就不太能转的动。
考虑到 \dbinom {|T|-1}{k-1}=\frac{|T|-1}{|T|-k}\dbinom{|T|-2}{k-1} ，所以我们可以在方程里及一个 l=|T| ，那就可以转了：
dp_{i,j,l}=dp_{i-1,j,l}-\frac{l-1}{l-k}dp_{i-1,j-p_i,l-1}
但是这个方程是 O(n^2m) 的，显然过不了，且没用到 k\leq10 的性质。
又考虑到 \dbinom {|T|-1}{k-1}=\dbinom{|T|-2}{k-1}+\dbinom{|T|-2}{k-2}
那么只需要在方程中记 l=k 即可转移：
dp_{i,j,l}=dp_{i-1,j,l}+dp_{i-1,j-p_i,l-1}-dp_{i-1,j-p_i,l}
就可以 O(nmk) 了。
子集反演
快速沃尔什变换（FWT）
快速莫比乌斯变换（FMT
拉格朗日反演
参考资料