组合计数记录

题单对应链接：https://www.luogu.com.cn/training/971456

# T1

P6475 [NOI Online #2 入门组] 建设城市

我们发现对于 $x$ 和 $y$ 的讨论是容易的，那我们可以考虑如何计算有 $k$ 个数，要求每个数 $\le num$ 且单调不降的方案数。

我们可以思考后发现，这似乎可以转化为要在 $k$ 个球之间插入 $num$ 个板，允许板与板之间为空的总方案数。

这就很板了，答案就是 $\binom {k+num-1} {k}$ 剩下的分讨即可。

# T2

P10138 [USACO24JAN] Cowmpetency G

我们可以考虑计算 $f_{i,j}$ 表示对于前 $i$ 个数，最大值为 $j$ 的所有合法方案，再用前缀和优化即可做到 $O(nc \log v)$。

我们可以考虑区间离散化，把它按照区间离散成点，这样就可以做到 $O(qc \log v)$。

# T3

P2182 翻硬币

似乎这个 DP 不是很难。

为了方便，我们令起始串为 $s$，终止串为 $t$。

我们发现，如果说状压来求的话复杂度是指数级别的，那我们需要考虑一个只有 $t$ 有的性质，其他数没有的。

这有个 trick 就是可以考虑状态与目标状态之间的不同，在这里就是考虑当前状态与目标状态之间有多少个点是不同的。

所以，我们可以定义 $f_{i,j}$ 表示在第 $i$ 轮中，我与目标 $t$ 有 $j$ 个位置不同的方案数。

这里，我们可以考虑一种我为人人的解法，只需考虑在原本不同的硬币里面有多少个硬币被翻面了。

转移是好想的：

$$f_{i,j+m-k \times 2} = f_{i,j} \times \binom {j} {k} \times \binom {n-j} {m-k}$$

其中 $k$ 是枚举的原本状态不同的硬币中被翻面的数量，答案就是 $f_{K,0}$。

# T4

AT_arc212_c [ARC212C] ABS Ball

关于一种计数的讨论、ARC212C Solution

# T5

CF1842G Tenzing and Random Operations

模拟赛时遇到的 trick，还是挺有意思的。

# 暴力

首先，可以考虑 $O(nm^2)$ 的暴力，可以定义状态为 $f_{i,j}$ 表示对于前 $i$ 个数，使用了 $j$ 次操作。

我们可以考虑一个人人为我的 DP。

我们可以枚举 $k$ 表示当前这个数使用了多少次操作，那转移就很明显了（为何我赛时没调出来）：

$$f_{i,j+k} = f_{i-1,j} \times \binom {k+j} {k} \times (a_i+val)$$

其中 $val$ 为 $(k+j) \times v$ 吗，最后求出 $n^m$ 的逆元即可。

# 正解

我们可以考虑将 $a_i+x \times v$ 看做有 $a_i+x \times v$ 条边链接 $i$ 和 $i-1$，求出方案数。

这一点我们可以发现它最多会产生 $n$ 条新加的边（即 $x \times v$），这引发我们可以重新定义 $f_{i,j}$。

定义 $f_{i,j}$ 表示当前到了 $i$ 号点，使用了 $j$ 条新加的边，这里我们可以考虑我为人人的 DP。

因为在加入这条边以后就可以无限制的使用，所以可以考虑这条边在哪里出现。

转移如下：

$$f_{i+1,j}=f_{i,j} \times (j \times v + a_{i+1}) \\ f_{i+1,j+1}=f_{i,j} \times (m-j) \times v \times (i+1)$$

答案即是 $\sum ^n _{i=0} f_{n,i} \times n^{m-i}$，最后处理一下 $n^m$ 的逆元即可。

# T6

P7961 [NOIP2021] 数列

赛时发现 $S$ 过大，不好判断，没考虑按位处理。

我们考虑定义 $f_{i,j,l,x}$ 表示当前处理好了 $S$ 的第 $i$ 位，此时向第 $i+1$ 位进位了 $j$ 并且前面有 $l$ 个 $1$ 以及确定了 $x$ 个 $a$。

这是一个我为人人的转移，我们发现对于 $f_{i,j,l,x}$ 我们来枚举下一个位置用 $y$ 个 $a$ 它可以转移到的位置其实就是 $f_{i+1,(j+y) \div 2,l+(j+y) \bmod 2,x+y}$ 但是 $a$ 是无序的，所以需要转移中要乘上 $\binom {n-x}{y} \times {v_{i+1}}^y$。

令最后一遍转移的位置是 $pos$，则答案就是：

$$\sum _{i=0} ^{k} f_{pos,0,i,n}$$

# T7

P2523 [HAOI2011] Problem c

因为不匹配是向后移动，所以我们无需考虑每一个人最后到底在哪。

思考无解的情况，发现只有当确定的人所在位置的后缀和 $sum_i > n-i+1$ 时才会无解（正确性显然）。

这里我们可以考虑对剩下的 $n-m$ 个人进行 DP。

设 $f_{i,j}$ 表示有 $j$ 个没确定位置的人的位置选在了 $i$ 到 $n$ 中，转移只需考虑位置 $i$ 有多少个人选择即可：

$$f_{i,j} = \sum _{k=0} ^{j} f_{i+1,j-k} \times \binom {j} {k}$$

预处理一下逆元即可，答案就是 $f_{1,n-m}$。

# T8

P9018 [USACO23JAN] Moo Route G

我们发现最优策略肯定是一次往返中所经过的点的数量越多越好，那这里我们就可以考虑对于位置 $i.5$ 所对答案造成的贡献。

• a_i \le a_

在这种情况下，经过了 $i.5$ 的边一定会经过 $(i-1).5$，对此，我们只需计算上一个点所经过的边（即 $a_{i-1}$）中选出 $a_i$ 即可。

• a_i \ge a_

在这种情况下，经过了 $(i-1).5$ 的边一定会经过 $i.5$，这时，我们只需要考虑经过 $i.5$ 的边中，插入以 $i$ 为起点的边的方案。

因为这之间有 $a_i - 1$ 个不同的位置，所以相当于是在 $a_i - 1$ 个位置中塞入 $a_i - a_{i-1}$ 个球。

总的方案：

$$\prod _{i=1} ^ {n-1} {\binom {a_{i-1}} {a_i} + \binom {a_i - 1} {a_i - a_{i-1}}}$$

# T9

CF1204E Natasha, Sasha and the Prefix Sums

模拟赛遇到的，第一眼就感觉要打表找规律，于是打了一个 $6 \times 6$ 的表（行为 $n$，列为 $m$），记 $f$ 表示答案：

0 0  0  0   0   0
1 1  1  1   1   1 
2 4  5  6   7   8 
3 9  16 22  29  37 
4 16 37 64  93  130 
5 25 71 149 256 386 

发现存在一个倒三角（ 1 5 22 93 386 往上走的三角形）满足杨辉三角的性质（$f_{i,j} = f_{i-1,j} + f_{i,j-1}$），这提示我们分开考虑。

对于前半段我们也考虑对于后半段的规律（即对 $f_{i-1,j} + f_{i,j-1}$）作差记为 $g$，剩下的 j 矩阵长这样：

0 0 0 0  0  0 
1 1 0 0  0  0 
1 2 2 0  0  0 
1 3 5 5  0  0 
1 4 9 14 14 0 

我们发现对于 $g_{i,i-1}$ 和 $g_{i,i-2}$ 相同，剩下的数为上一行同样位置的前缀和加一，即 $g_{i,j} = \sum _{k=1} ^ {j} g_{i-1,k}$。

用 $g_{i,j}$ 完善 $f_{i,j}$ 的转移即可。

还有一种 $O(n+m)$ 的做法：

考虑定义 $f_i$ 表示对于最终最大值 $\ge i$ 的所有方案，最后答案即是 $\sum _{i=1} ^{n} f_i$（因为这里记录的是 $\ge i$ 的所有方案，对于最大值为 $i$ 的所有排列，最后会恰好被算 $i$ 次）。

如果 $(0,0)$ 和 $(n+m,n-m)$ 在 $y=i$ 的左右两边则答案就是从 $(0,0)$ 到 $(n+m,n-m)$ 的方案数。

如果不是，把 $(0,0)$ 翻上去就好了，即从 $(0,2 \times i)$ 到 $(n+m,n-m)$ 的方案数。

# T10

P12917 [POI 2021/2022 R3] 小矮人派对 2 / Impreza krasnali 2

和 42pts 一样，考虑单独处理没出现的数（数量记为 $k$），考虑 DP 处理，因为这个数要考虑 $i-1,i,i+1$ 三个位置，所以状态定义要有 5 层转移，定义 $f_{i,0/1/2/3/4}$ 分别表示：

1. $a_i \to i$
2. $a_i \to i-1 \ \& \ a_{i-1} \not \to i$
3. $a_i \to i-1 \ \& \ a_{i-1} \to i$
4. $a_i \to i+1 \ \& \ a_{i-1} \to i$
5. $a_i \to i+1 \ \& \ a_{i-1} \not \to i$

分情况考虑即可：

1. a_i = a_{i-1} = a_

$$f_{i,1} = f_{i-1,0}$$

2. a_i = a_{i-1} \not = a_

$$f_{i,1} = f_{i-1,2} \\ f_{i,2} = f_{i-1,3}$$

3. a_i = a_{i-1} \not = a_

$$f_{i,0} = f_{i-1,3} + f_{i-1,4} \\ f_{i,1} = f_{i-1,0}$$

4. a_i \not = a_{i-1} \ \& \ a_i \not = a_

$$f_{i,0} = f_{i-1,0} + f_{i-1,1} + f_{i-1,2} \\ f_{i,1} = f_{i-1,1} \\ f_{i,2} = f_{i-1,4} \\ f_{i,3} = f_{i-1,3} + f_{i-1,4} \\ f_{i,4} = f_{i-1,0} + f_{i-1,1} + f_{i-1,2}$$

最后答案就是：

$$(f_{n,0} + f_{n,1} + f_{n,2}) \times \prod ^{k} _{i=1} i$$

# T11

P9374 「DROI」Round 2 单图

发现合法的单图是由二元环和最长链长度不超过二的图组成。

考虑分别处理二元环和链的情况。

对于二元环，定义 $g_i$ 表示对于有 $i$ 个点的二元环的所有方案，转移应当是显然的：

$$g_i = g_{i-1} \times (i-1)$$

考虑对于链的情况，定义 $f_i$ 表示对于有 $i$ 个点的链的所有方案数：

$$f_i = \sum _{j = 0} ^{i - 1} \binom {i} {j} \times (2^{i-j} - 1) ^ j$$

答案只需枚举有多少个二元环即可即：

$$ans = \sum _{i = 0} ^{\lfloor \frac{n}{2} \rfloor} f_{n - 2i} \times g_{2i} \times \binom {n} {2i}$$

# T12

P3643 [APIO2016] 划艇

考虑 31pts，发现可以记录每一个值 $j$，小于它的值的个数，这个用离散化 + 树状数组即可完成。

推到 100pts，考虑区间离散化，记录对于区间 $(l,r]$ 这个范围内的方案的个数，还是树状数组维护。

但这样只能拿到 31pts，因为没有考虑有多个点在同一个区间的情况。

考虑定义 $f_{i,j}$ 表示第 $i$ 个学校内在区间 $j$ 内的方案数。

考虑枚举与这同一块内这一位前有多少个数即可。