组合计数记录

题单对应链接：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$ 的逆元即可。