组合计数记录

题单对应链接：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}}}$$