组合计数杂题

ABC276G

【题意】
给定 \(n, m\)，求出满足以下条件的数列的个数：

• 数列长度为 \(n\)。
• 数列的每一个数都在 \([0,m]\) 之间。
• 数列的相邻两个数模 \(3\) 不同余。

【思想】
组合计数问题，需要利用一些一一映射，将要算的东西改写成能算的东西，比如 \(\binom{n}{k}, \begin{Bmatrix}n\\k\end{Bmatrix},\begin{bmatrix}n\\k\end{bmatrix}\)（选择，子集，轮换）。

【分析】
“模 \(3\) 不同余”这个条件首先一看就不是很好直接算，我们考虑构造差分数组 \(b\)，满足对于 \(i \in [2,n]\) 有 \(3 \nmid b_i\)。

然后显然考虑拆分成 \(b_i / 3\) 和 \(b_i \% 3\)。记 \(x_i = b_i \% 3, y_i = b_i / 3\)，则有对于 \(i = 1\)，\(x_i \in \{0,1,2\}\)；对于 \(i > 1\)，\(x_i \in \{1,2\}\)。

我们先考虑整块，也就是钦定了一套 \(x_i\) 之后，\(y_i\) 的个数怎么算？也就是计算使得 \(\sum \limits_{i = 1} ^ n y_i \le \lceil \cfrac{m - \sum x_i}{3} \rceil\) 的方案数。可以发现这个东西只和 \(\sum x_i\) 有关，那么如果计算上述式子的时间为 \(T\)，那么我们可以枚举 \(x_i(i \le [2,n])\) 存在多少个 \(1\)，从而得到存在多少个 \(2\)。相同的方案数可以二项式求出，那么可以 \(O(n) \times T\)。

那么问题转化为：计算使得 \(\sum \limits_{i = 1} ^ n y_i \le t\) 的方案数。我们知道 \(\sum \limits_{i = 1} ^ n y_i = t\) 的方案数是插板法算的，那么一种方法是预处理出所有 \(t\) 的答案，那么每次询问可以 \(O(1)\) 得到解。总时间复杂度 \(O(n \log t_{\max} + n) = O(n \log t_{\max})\)，其中 \(t_{\max} \sim m\)。

还有一种方法：

引理：\(y_i\) 都是自然数，使得 \(\sum \limits_{i = 1}^n y_i \le t\) 的方案数为 \(\binom{n + t}{n}\)。

证明：考虑插板法的过程。对于 \(\sum \limits_{i = 1}^n y_i = t\) 的方案数，也就相当于 \(t + n\) 个球，插 \(n - 1\) 个板，分成 \(n\) 个区域。

那么我们可以增加一个区域，这个区域表示把这些球扔掉，其他 \(n\) 个区域表示分成的 \(n\) 个区域。那么也就是把 \(\le t\) 个球分成 \(n\) 个区域。因此是一共 \(t + n + 1\) 个球，插 \(n\) 个板，分成 \(n + 1\) 个区域，答案为 \(\binom{n + t}{n}\)。