数学 - 浅谈组合计数

[JXOI2018] 游戏

如果一个数 $i$ 不能表示为区间 $l,r$ 内某个数的倍数，那么它是一定要被访问的，称这种数字为关键数。

由于所有的关键数都要被检查，所以对于一个固定的 $p$，设关键数的最后一个位置为 $k$，那么 $t(p)\ge k$。

反之，又因为访问了所有的关键数后，不可能还有人没被通知，这里反证法不难证明，那么 $t(p)\le k$，于是 $t(p)=k$。

设关键数的数量为 $m$，那么枚举 $t(p)$ 的值即可求出所有 $t(p)$ 之和。

$$\sum_{i=m}^n \binom{i-1}{m-1} m!(n-m)!$$

事实上上面的公式足以通过本题，但是它有封闭形式，并且不是特别好推导，所以我们继续看一下怎么变换一下视角。

对于 $n!$ 种排列，都有 $m$ 个关键数将其划分为 $m+1$ 段，设每段非关键数的数量为 $x_1,x_2,\dots,x_{m+1}$，那么答案显然是：

$$\sum_{p} n-x_{m+1}$$

由对称性，我们可以得出：

$$\sum_p x_1=\sum_p x_2=\cdots=\sum_p x_{m+1}$$

又因为 $\sum x_i=n-m$ 为定值，因此我们可以得到：

$$\sum_p x_{m+1} =\frac{n-m}{m+1} n!$$

因此有原式：

$$\sum_p n-x_{m+1}=\frac{m}{m+1}(n+1)!$$

复杂度类似埃筛 $O(n\log \log n)$，但是这里关键数也并不是真正的素数，然而也不会超过 $O(n\log n)$，所以问题不大。

[FJOI2017] 矩阵填数

对于这种计数合法方案数的问题，我们通常可以设计一种方式，使得合法方案的贡献为 $1$，非法方案的贡献为 $0$，然后交换求和号，对满足这个贡献要求的方案进行计数。

设 $A$ 需要满足 $n$ 种条件，一个常用的方法是 $\sum_{A\in U} \sum_{T\subseteq[n]} (-1)^{|T|}[A \operatorname{violates} T]$，这样一来如果 $A$ 违反了 $k$ 种条件，它的贡献就会变为 $\sum_{i=0}^k \binom{k}{i}(-1)^i =[k=0]$，即只有 $k=0$ 时会产生 $1$ 的贡献，否则产生 $0$ 的贡献。

回到本题，设全集 $U$ 表示所有子矩形最大值 $\le v_i$ 的矩阵，违反条件 $i$ 定义为这个子矩形最大值 $\le v_i-1$。

于是我们就可以进行计数：

$$\sum_{T\subseteq[n]}(-1)^{|T|}\sum_{A\in U} [A\operatorname{violates} T]=\sum_{T\subseteq[n]}(-1)^{|T|}\prod_{i=1}^h\prod_{j=1}^w U_{T,i,j}$$

其中 $U_{T,i,j}$ 表示违反集合 $T$ 中的条件时，格子 $i,j$ 的最大值。

我们可以对矩形中的点离散化，并且按照每个矩形的要求从小到大排序，每次执行给矩形赋值为 $1$ 以及查询 $0$ 的数量两种操作。

直接暴力统计即可，复杂度 $O(n^32^n)$。

[P8863] 构造数组

本题统计的方案数，等价于把 $b_1$ 个 $1$，$b_2$ 个 $2$，直到 $b_n$ 个 $n$ 这 $m=\sum_i b_i$ 个数排成一列 $c_1,c_2,\dots, c_m$ 并且满足 $c_{2k-1}<c_{2k}$ 的方案数，注意 $m$ 为奇数时答案显然为 $0$。

我们可以只计数 $c_{2k-1}\neq c_{2k}$ 的所有方案，最后统一除掉 $2^{m/2}$ 使得 $c_{2k-1}<c_{2k}$。

由于这里有相同的元素，我们先人为给它们进行标号，让它们变为不同的元素，最后强制要求同一类元素的标号递增，从而让它们与相同的情况建立起一个一一对应。

化到现在就可以进行贡献的设计了，设一共有 $m/2$ 个条件，违反条件 $i$ 定义为 $c_{2i-1}=c_{2i}$，全集 $U$ 定义为这些互不相同的元素的全排列。

虽然这里写的是 $c_{2i-1}=c_{2i}$，但是我们计数的时候仍然认为这两个元素是不同的，只是它们的值相同，但是被我们人为进行了标号。

于是进行计数：

$$\sum_{T\subseteq[m/2]} (-1)^{|T|}\sum_{x_1+\cdots+x_n=|T|} \left(\prod_{i=1}^n\binom{b_i}{2x_i}\frac{(2x_i)!}{x_i!} \right) |T|!(m-2|T|)!$$

这里对内部式子进行解释：从 $b_i$ 个同类元素选出 $2x_i$ 个元素，并且给它们进行全排列后，除掉每一个 Pair 的顺序。最后通过 $|T|!$ 给所有 Pair 进行全排列。

注意到后面式子只关心 $|T|$，所以我们进一步优化，只枚举 $j=|T|$：

$$\sum_{j=0}^{m/2}(-1)^{j}\binom{m/2}{j}\sum_{x_1+\cdots+x_n=j} \left(\prod_{i=1}^n\binom{b_i}{2x_i}\frac{(2x_i)!}{x_i!} \right) j!(m-2j)!$$

中间是一个卷积的形式，可以直接用背包 $O(m^2)$ 求解，因为这里第 $i$ 次枚举只会枚举到 $\sum_{j=1}^i b_j/2$，所以常数比较小，即使 $m=3\times 10^4$ 也还好。

求出这个值之后，我们只需要除掉 $2^{m/2}$ 后，再除掉 $\prod_{i=1}^n b_i!$ 消除同一类元素顺序的影响后就是答案。

复杂度 $O(n+m^2)$。

[P8321] 沈阳大街 2

为了消除 $\min$ 的影响，我们按照从大到小放数的方式，设 $S_i,T_i$ 分别表示前缀中来自 $A,B$ 的数量。

具体地说，设 $dp_{i,j}$ 表示前 $i$ 个数中已经配对了 $j$ 对的权值之和。

这里转移时比较巧妙的一点是，如果当前元素 $v_i$ 来自 $A$，那么 $dp_{i,j}$ 的状态时前面剩下 $T_i-j$ 个 $B$ 类元素；反之有 $S_i-j$ 个 $A$ 类元素。也就是说我们根据状态就可以得知一些元素的数量，同样的情况在下面的一道题目中也有出现。

来自 $A$ 时的转移是 $dp_{i,j}=dp_{i-1,j}+v_i(T_i-j+1)dp_{i-1,j-1}$，来自 $B$ 时同理。

注意这里是 $dp_{i-1,j-1}$，所以有 $T_i-j+1$ 个 $B$ 类元素。

最终答案是 $dp_{2n,n}$，复杂度 $O(n^2)$。

[P8859] 冒泡排序

先考虑普通排列的情况。

对于一个固定的排列，我们从左到右动态维护前缀是一个升序序列，那么如果当前元素的前面有比它更大的元素，我们就可以通过一次冒泡操作把它放到正确的位置上，这样我们构造出了一种次数为 $n-A$ 的方案，其中 $A$ 是前缀最大值的数量。

反之，如果一个元素不是前缀最大值，那么如果不操作它，最终它的左边一定仍然存在比它大的元素，所以 $n-A$ 同样是下界。

因此我们只需要设 $f_{i,j}$ 表示长度为 $i$ 的排列中前缀最大值有 $j$ 个的排列的数量。

转移考虑从大到小插入元素，这样只有当插入到开头时才会使得前缀最大值的数量增加，其余情况均不改变最大值数量。

现在考虑圆排列，不难猜测是 $n$ 种开头的普通排列的操作次数取 $\min$，但是这个证明比较麻烦。

设共移动了 $q$ 次，并且 $i$ 次操作后 $n$ 种开头的 $A$ 的最大值为 $B_i$，那么 $B_q=n$。

假设第 $i$ 次操作的元素是 $x$ 向前移动了若干位置，即 $a_1a_2\dots a_kx\to xa_1a_2\dots a_k$，我们以 $x$ 最终到达的位置作为开头，考察 $n$ 种开头的 $A$ 值变化如何。

1. 对于 $x$ 这个位置，只有 $x$ 有可能成为新的前缀最大值，$A$ 最多增加 $1$；
2. 对于 $a_1,a_2,\dots, a_k$ 这些位置，$A$ 最多增加 $0$，这是因为 $x<a_1,a_2,\dots,a_k$，所以 $x$ 并不会导致新的前缀最大值出现。
3. 对于其它位置，$A$ 最多增加 $1$，因为只有 $x$ 有可能成为新的前缀最大值，理由依旧如上。

因此 $B_i-B_{i-1}\le 1$，那么 $n-B_0=B_q-B_0\le q$，也就是说 $q\ge n-B_0$，而我们以 $B_0$ 对应的位置进行操作就可以达到 $n-B_0$ 次，所以这个最小值是能够取到的。

接下来我们固定 $n$ 放到最后，这是因为 $n$ 作为最大值可以对前缀最大值进行截断。那么一个圆排列的 $B$ 值就是固定 $n$ 为结尾后，这个普通排列所有后缀的前缀最大值数量的最大值。设一个排列 $p$ 的这个值为 $Q(p)$。

此时我们成功将圆排列的问题转化为普通排列的问题。

依旧考虑最大值会截断这个特殊的性质，这让我们考虑从大到小放数，假设最大值左侧是 $p$，右侧是 $q$，最大值本身是 $x$，那么 $Q(pxq)=\max(Q(p)+1,Q(q))$。

于是设 $f_{i,j}$ 表示 $1\sim i$ 的排列中，$Q(p)=j$ 的 $p$ 的数量，那么可以进行转移：

$$f_{i,j}=\sum_{k=1}^i \sum_{\max(a+1,b)=j} \binom{i-1}{k-1}f_{k-1,a}f_{i-k,b}$$

考虑让 $f$ 本身带上组合数提供的项，那么这个转移式可以被化简为：

$$\begin{aligned} \frac{f_{i,j}}{i!}&=\frac{1}{i}\sum_{k=1}^i \sum_{\max(a+1,b)=j} \frac{f_{k-1,a}}{(k-1)!}\frac{f_{i-k,b}}{(i-k)!}\\ &=\frac{1}{i}\sum_{k=1}^{i} \left(\frac{f_{k-1,j-1}}{(k-1)!}\sum_{b\le j} \frac{f_{i-k,b}}{(i-k)!}+\frac{f_{i-k,j}}{(i-k)!}\sum_{a<j-1}\frac{f_{k-1,a}}{(k-1)!}\right) \end{aligned}$$

前缀和优化就可以做到 $O(n^2k)$。

[P8558] 黑暗

枚举走到平面 $z=0$ 的点，$(x,y,0)$将这个概率乘 $1/3$ 就是在这个点撞墙的概率。

对于恰好在坐标轴上的点，会在枚举两个平面时被枚举到两次，那么恰好它本身乘 $2/3$ 就是在这个点撞墙的概率，所以我们不需要特殊考虑在轴上的点。原点同理。

那么我们只需要解决走到 $z=0$ 的情况即可，其余三种都是对称的。

考虑每一步有三种选择，不难写出下面的表达式：

$$\sum_{x=0}^{A}\sum_{y=0}^B \frac{\binom{A-x+B-y+C}{A-x}\binom{B-y+C}{B-y}}{3^{A-x+B-y+C}}\frac{1}{3}(x+y)^k$$

观察到 $x+y$ 多次同时出现，于是我们把他们打包为 $t$ 进行换元操作。

$$\begin{aligned} E&=\sum_{t=0}^{A+B}\frac{t^k}{3^{A+B+C-t+1}}\sum_{x=0}^{\min(t,A)} \binom{A+B+C-t}{A-x}\binom{B+C-(t-x)}{B-(t-x)}\\ &=\sum_{t=0}^{A+B}\frac{t^k}{3^{A+B+C-t+1}}\sum_{x=0}^{\min(t,A)} \frac{(A+B+C-t)!}{(A-x)!(B-t+x)!C!}\\ &=\sum_{t=0}^{A+B}\frac{t^k(A+B+C-t)!}{3^{A+B+C-t+1}C!(A+B-t)!}\sum_{x=0}^{\min(t,A)} \frac{(A+B-t)!}{(A-x)!(B-t+x)!}\\ &=\sum_{t=0}^{A+B}\frac{t^k(A+B+C-t)!}{3^{A+B+C-t+1}C!(A+B-t)!}\sum_{x=0}^{t} \binom{A+B-t}{A-x} \end{aligned}$$

为啥最后上标变成 $t$ 了呢？因为当 $x>A$ 时，组合数的下指标为负数，我们记这种非法组合数为 $0$，而组合数递推的等式在这种意义下仍然成立，这也是这种题目通常避免分类讨论的好方法。

现在的问题就是如何快速求出 $F_t=\sum_{x=0}^t \binom{A+B-t}{A-x}$，其中 $t$ 从 $0$ 取到 $A+B$。

当 $t\ge 1$ 时，可以写出：

$$\begin{aligned} F_{t-1}&=\sum_{x=0}^{t-1}\binom{A+B-t+1}{A-x}\\ &=\sum_{x=0}^{t-1}\binom{A+B-t}{A-x} +\binom{A+B-t}{A-x-1}\\ &=F_t-\binom{A+B-t}{A-t}+F_t-\binom{A+B-t}{A}\\ &=2F_t-\binom{A+B-t}{A-t}-\binom{A+B-t}{A}\\ \end{aligned}$$

设 $V=A+B+C$，我们只需要预处理出 $V$ 以内的阶乘与阶乘逆，以及 $t^k$ 即可，其中 $t^k$ 可以线性筛预处理，这样只会对质数调用快速幂，这样下来预处理复杂度就会是 $O(\pi(V)\log k+V)$，计算主要的和式的复杂度是 $O(V)$。

[JSOI2015] 染色问题

这道题目有助于理解钦定与恰好之间的转化到底是在干啥。

观察到有三个限制，分别是每行非空，每列非空，每种颜色出现一次。

硬做显然没啥前途，所以我们应该放宽限制然后通过二项式反演把放宽后的限制转化为恰好。

钦定几行不涂色、钦定几个颜色不出现是容易做的，所以我们设出第一个计数：$f_{i,k}$ 表示每列非空，钦定 $i$ 行不涂色，钦定 $k$ 个颜色不出现的方案数。

$$f_{i,k}=\binom{C}{k}\binom{n}{i}((C-k+1)^{n-i}-1)^m$$

那么 $g_{i,k}$ 表示每列非空、恰好 $i$ 行不涂色，钦定 $k$ 个颜色不出现的方案数，有 $f$ 与 $g$ 的关系如下：

$$f_{i,k}=\sum_{j=i}^n \binom{j}{i} g_{j,k}$$

右边的式子可以理解为枚举所有每列非空、钦定 $k$ 个颜色不出现的涂色方案，用恰好 $j$ 行不涂色来把所有方案进行不重不漏的划分，然后计算每一种方案会对 $f_{i,k}$ 产生的贡献。

接下来，设 $h_{i,k}$ 表示每列非空、恰好 $i$ 行不涂色，恰好 $k$ 个颜色不出现的方案数，有 $g$ 与 $h$ 的关系如下：

$$g_{i,k}=\sum_{j=k}^C \binom{j}{k} h_{i,j}$$

那么进行两次二项式反演，得到最终 $h_{0,0}$ 的值即可，化简如下：

$$\begin{aligned} h_{i,k}&=\sum_{j=k}^C(-1)^{j-k}\binom{j}{k}g_{i,j}\\ &=\sum_{j=k}^C \sum_{l=i}^n (-1)^{j-k+l-i}\binom{l}{i}\binom{j}{k} f_{l,j}\\ &=\sum_{j=k}^C \sum_{l=i}^n (-1)^{j-k+l-i}\binom{l}{i}\binom{j}{k}\binom{C}{j}\binom{n}{l}((C-j+1)^{n-l}-1)^m \end{aligned}$$

代入 $h_{0,0}$，有：

$$h_{0,0}=\sum_{j=0}^C \sum_{l=0}^n (-1)^{j+l}\binom{C}{j}\binom{n}{l}((C-j+1)^{n-l}-1)^m$$

复杂度 $O(n^2\log n)$，将 $n,m,C$ 视作同阶。

[HAOI2018] 染色

钦定 $i$ 个颜色恰好出现 $S$ 次的方案有 $f_i$ 种，那么有：

$$f_i=\binom{M}{i}\prod_{j=0}^{i-1} \binom{N-jS}{S}(M-i)^{N-iS}=\binom{M}{i}\frac{N!(M-i)^{N-iS}}{(S!)^i(N-iS)!}$$

那么恰好 $i$ 个颜色出现 $S$ 次的方案有 $g_i$ 种，那么有：

$$f_i=\sum_{j=i}^{M} \binom{j}{i} g_j$$

二项式反演，可以得到：

$$\begin{aligned} g_i&=\sum_{j=i}^M (-1)^{j-i}\binom{j}{i} f_j\\ &=\sum_{j=i}^M (-1)^{j-i}\frac{j!f_j}{i!(j-i)!} \end{aligned}$$

设 $h_j=(M-j)!f_{M-j}$，那么就有：

$$\begin{aligned} g_i&=\frac{1}{i!}\sum_{j=i}^M (-1)^{j-i}\frac{h_{M-j}}{(j-i)!}\\ &=\frac{1}{i!}\sum_{j=0}^{M-i} \frac{(-1)^j}{j!} h_{M-j-i} \end{aligned}$$

那么 $g_i$ 是一个标准的卷积形式，复杂度就是 $O(m\log m+n)$。

[NOI Online #2 提高组] 游戏

设 $f_i$ 为钦定出现 $i$ 次非平局回合数的方案数，$g_i$ 为恰好出现 $i$ 次非平局回合数的方案数。

问题是，如何求出 $f_i$。设 $dp_{u,j}$ 表示在 $u$ 的子树内，选出 $j$ 个非平局点对的方案数。

首先，如果 $u$ 不选，那么这是一个树上背包形式的转移，这里不再赘述。

其次，如果 $u$ 选，不妨设 $u$ 是 $0$ 类点，那么后代需要在没有被选的 $1$ 类点中再选一个，设 $A_u$ 表示 $u$ 子树内 $1$ 类点的数量，转移如下：

$$ndp_{u,j}=dp_{u,j}+dp_{u,j-1}(A_u-j+1)$$

这里很好的用到了 $j-1$ 这个状态是所有选择 $j-1$ 个点对的方案数这一定义。

那么之后呢？我们终于可以计算 $f_i$ 了，式子如下：

$$f_i=\binom{m}{i}dp_{1,i} i!(m-i)!(m-i)!=m!(m-i)!dp_{1,i}$$

这里的含义是，我们先从 $m$ 局选 $i$ 局放下一个非平局的选法，并且给它们全排列；剩下 $m-i$ 个点对，我们先计数它们配对的方案，有 $(m-i)!$ 种，然后再把它们放到 $m-i$ 局进行一个全排列。

但是，这个题目中定义两种方案不同的方式是相对于 $A$ 选择的点来说的，也就是说，我们需要除掉一个 $m!$，避免给 $A$ 的选择进行全排列，即真正的 $f_i$ 式子应当是：

$$f_i=(m-i)!dp_{1,i}$$

接下来直接套二项式反演的式子即可，复杂度 $O(n^2)$。