计数杂题

部分题目来自这个题单。

Luogu P6075 [JSOI 2015] 子集选取

首先，发现可以把元素单独拎出来考虑，假设对于一个元素来说有 $𝑥$ 种放置方案，则答案为 $𝑥 𝑛$ 。

继续转化题意。

对于 $𝐴 𝑖, 𝑗$ ，它必须是它左边集合的子集，也得是上边集合的子集。
也就是说，如果 $𝐴 𝑖, 𝑗$ 包含元素 $𝑥$ ，则在它正上方、左上方、左侧的所有集合都包含 $𝑥$ 。（形式化来说，即 $𝐴 𝑎, 𝑏, 1 ⩽ 𝑎 ⩽ 𝑖, 1 ⩽ 𝑏 ⩽ 𝑗$ 均包含 $𝑥$ ）

然后想象一种合法方案，容易发现每种方案就相当于把整个三角形分成两半，左上一半右下一半。

每两种方案不同当且仅当左上右下的分界线不同。

于是我们就能很轻松地求方案数了，即一个分界线从左下走到右上的方案。每一步可以向左或者向右走，即 $2 𝑘$ 。

快速幂即可。

Luogu P6146 [USACO 20 FEB] Help Yourself G

首先为了划分未求解和已求解的部分，我们需要把线段按照左端点排序。

给一个不排序会遇到错误的例子：

1 2	---- 1 ------3 --------- 2 复制

用下面的做法做的话，先算 $1, 3$ 和先算 $1, 2$ 是不一样的，可以自己体会一下。

然后设 $𝑓 𝑖$ 为前 $𝑖$ 个线段的答案。为什么只有一维？因为容易发现子集这个东西很难用来划分阶段。另外前面的排序已经使得这种状态划分是唯一的了。

考虑如何推出 $𝑓 𝑖$ 。

$𝑓 𝑖$ 的答案由两部分组成：

前 $𝑖 - 1$ 个线段的答案 $𝑓 𝑖 - 1$
前面所有子集加上第 $𝑖$ 条线段的答案。

发现后者实际上也是分两部分的：

新增的连通块（复杂度）
除去新增，也就是原有的复杂度 $𝑓 𝑖 - 1$

好了，那么新增的连通块怎么算？实际上就是与第 $𝑖$ 条线段不相交的前 $𝑖 - 1$ 条线段的子集的数量。为啥呢？
那我们可以把前 $𝑖 - 1$ 条线段的子集分两类：与 $𝑖$ 相交与不相交。显然相交的子集不会贡献答案，不相交的子集会且仅会贡献 $1$ 的答案。

然后问题就转化为：对前 $𝑖 - 1$ 条线段与线段 $𝑖$ 不相交的子集计数。
容易发现就是与线段 $𝑖$ 不相交的所有线段集合 $𝕏$ 的子集数量，计数就是 $2 | 𝕏 |$

得到递推式：

$𝑓 𝑖 = 2 𝑓 𝑖 - 1 + 2 | 𝕏 |$

$𝕏$ 的大小我们可以预处理出来：统计每一个右端点出现的次数 $𝑠 𝑖$ ，然后做一个前缀和，最后 $𝑠 𝑖 - 1$ 就是不覆盖点 $𝑖$ 的线段数量。

用快速幂优化，复杂度 $O (𝑛 l o g 𝑛 + 𝑛 l o g 𝑛)$ ，如果用光速幂可以干到 $O (𝑛 l o g 𝑛 + 𝑛 + \sqrt 𝑛)$ 。

P6008 [USACO 20 JAN] Cave Paintings P

首先发现答案就是把每个连通块的方案数乘起来。

那对于一个连通块怎么算答案？一个比较蛋疼的事实是，即使是同一个连通块，我们也不能保证它每个部分的水位是一样的，比如下面这个例子：

########
###  ###
#      #
#  ##  #
#  ##  #
########

复制

显然左右侧在分割开的时候可以水位高度不同。

那我们能不能对分割开的两块分别算呢？答案是不行，因为连通器原理。

########
#  ##  #
#  ##  #
#      #
#      #
########

复制

初中物理可知，左右两侧水位必须一样高。

所以我们需要动态维护这个关系，用啥呢？并查集。

初始化每个格子答案为 1，然后对于每个连通块从下往上涨水，过程如下：

把这一行相邻的能放水的位置连在一起，表示他们必须是一个水位的。
遍历该行每一个空位，如果这个位置下面也是空位且二者目前没有相连，那么当前位置方案数 *= 正下方一格方案数，同时把两个格子相连，表示两个连通块接在一起了。
遍历该行每一个空位，每遇到一个连通块（find(x) == x）就把该格方案数加一。

最后用前面提到过的判断连通块的方式把答案乘起来就好了。

Luogu P1350 车的放置

同样是蓝题，但是比上一道水多了。

每一行每一列都只能放一个棋子，那直接从上往下遍历行，同时枚举放几颗棋子递推计数即可。

具体来说，设 $𝑓 𝑖, 𝑗$ 为前 $𝑖$ 行放了 $𝑗$ 个棋子的方案数量，则转移方程如下：

$𝑓 𝑖, 𝑗 = 𝑓 𝑖 - 1, 𝑗 + 𝑓 𝑖 - 1, 𝑗 - 1 (𝑙 𝑒 𝑛 - 𝑗 + 1)$

其中 $𝑙 𝑒 𝑛$ 是行长度。

记得把 $𝑓 0 \sim 𝑏 + 𝑑, 0$ 设为 $1$ 。

Luogu P3223 [HNOI 2012] 排队

基本上是纯数学题。

大概计数题可以分两种大方向思考：正推、容斥。

而容斥也大概分两种：手动容斥和套式子反演。

想直接拆分算，感觉是一个非常恶心难想的分类讨论。

递推，设 $𝑓 𝑛, 𝑚$ 为 $𝑛$ 男生 $𝑚$ 女生的方案数，发现推不了。

那就手动容斥。
容易发现把老师的限制扔掉之后是可以轻松算出来答案的： $𝐴 𝑚 𝑚 𝐴 𝑛 + 2 𝑛 + 2 (𝑛 + 3 𝑚)$ ，即把老师当成男生随便放置，然后在他们中间的空隙中选出来 $𝑚$ 个用来放女生。

然后不合法方案，即两个老师靠在一起的方案，把两个老师绑在一起当一个男生求出来所有合法方案即可。别忘了两个老师顺序可以变，所以加一个 $𝐴 22$ 。

最终答案： $𝐴 𝑚 𝑚 𝐴 𝑛 + 2 𝑛 + 2 (𝑛 + 3 𝑚) - 𝐴 𝑚 𝑚 𝐴 𝑛 + 1 𝑛 + 1 (𝑛 + 2 𝑚) 𝐴 22$

为啥说基本上是纯数学题而不是完全的数学题？因为这题需要打高精。

然后我用 python 写的，python 整数除法返回浮点值，所以要强制整除，即使用 //。

举个例子，算 $(𝑛 𝑚)$ ：

import math

def binom(n, m) -> int:
    if n < m:
        return 0
    else:
        return math.factorial(n)//math.factorial(m)//math.factorial(n-m)

复制

[CSP-S 2019] Emiya 家今天的饭

挺难的题。

首先我们可以把选菜看成从方阵里面选数，每行只能选一个，每列最多选 $⌊ 𝑘 2 ⌋$ 个。

如果我们分列来考虑，发现合法的列有很多，但是不合法的列只会出现一个。（显然选的数超过总数一半的列只会有一个吧）
换句话说，如果我们正着算，记录合法方案总数，是一件非常困难的事情，因为每一列的合法情况我们都要记录。但是相对的，对于不合法方案计数，我们可以枚举不合法的列进行递推。当我们保证这一列不合法时，其他列一定合法，这样我们就不用记太多状态了。

枚举到第 $𝑐 𝑜 𝑙$ 行，设 $𝑓 (𝑐 𝑜 𝑙) 𝑖, 𝑗, 𝑘$ 为第 $𝑐 𝑜 𝑙$ 列为不合法列，前 $𝑖$ 行，第 $𝑐 𝑜 𝑙$ 行选了 $𝑗$ 个数，其他行选了 $𝑘$ 个数的方案数量， $𝑠 𝑖$ 为第 $𝑖$ 行 $𝑎$ 的总和，则有转移方程：

$𝑓 𝑖, 𝑗, 𝑘 = 𝑓 𝑖 - 1, 𝑗, 𝑘 + 𝑓 𝑖 - 1, 𝑗 - 1, 𝑘 \cdot 𝑎 𝑖, 𝑐 𝑜 𝑙 + 𝑓 𝑖 - 1, 𝑗, 𝑘 - 1 \cdot (𝑠 𝑖 - 𝑎 𝑖, 𝑐 𝑜 𝑙)$

然后不合法方案数即 $\sum 𝑗 > 𝑘 𝑓 (𝑐 𝑜 𝑙) 𝑛, 𝑗, 𝑘$

复杂度 $Θ (𝑚 𝑛 3)$ ，想办法减少状态。

根据刚才不合法方案数的计算，我们发现，一个方案不合法，当且仅当有一列选的数大于其他列选的数之和。

换句话说，刚才对不合法方案数的统计，基于 $𝑗 > 𝑘$ 这个条件，那我们是不是可以只记录 $𝑗 - 𝑘$ 这个东西呢？

设 $𝑓 (𝑐 𝑜 𝑙) 𝑖, 𝑗$ 为第 $𝑐 𝑜 𝑙$ 列为不合法列，前 $𝑖$ 行，当前行选的数比别的行多 $𝑗$ 个的总方案数，转移方程和上面的差不多：

$𝑓 𝑖, 𝑗 = 𝑓 𝑖 - 1, 𝑗 + 𝑓 𝑖, 𝑗 - 1 \cdot 𝑎 𝑖, 𝑐 𝑜 𝑙 + 𝑓 𝑖, 𝑗 + 1 \cdot (𝑠 𝑖 - 𝑎 𝑖, 𝑐 𝑜 𝑙)$

不合法方案数： $\sum 𝑗 > 0 𝑓 (𝑐 𝑜 𝑙) 𝑛, 𝑗$

容易发现这个东西可能是负数，所以实现的时候要给 $𝑗$ 这一维加一个 $𝑛$ 。

然后是计算总方案数，设 $𝑔 𝑖, 𝑗$ 为前 $𝑖$ 行选了 $𝑗$ 个数的方案数，转移方程：

$𝑔 𝑖, 𝑗 = 𝑔 𝑖 - 1, 𝑗 + 𝑔 𝑖 - 1, 𝑗 - 1 \cdot 𝑠 𝑖$

最终答案： $\sum 𝑛 𝑖 = 1 𝑔 𝑛, 𝑖 - \sum 𝑚 𝑐 𝑜 𝑙 = 1 \sum 𝑛 𝑗 > 0 𝑓 (𝑐 𝑜 𝑙) 𝑛, 𝑗$

Luogu P3214 [HNOI 2011] 卡农

题意要求选取子集有三条限制：
- 非空 - 选出的子集两两不同 - 所有元素的出现次数为偶数

转化 1：将“子集”转化为“二进制数”，然后选取子集变成从 $0, 1 \dots 2 𝑛 - 1$ 个数里面选出 $𝑚$ 个，然后限制就变成了：
- 这些数不等于 $0$ - 这些数异或和为 $0$ - 这些数两两不同

转化 2：答案是“无序”的方案数，我们发现这个 $𝑚$ 个数无序的方案数乘一个排列 $𝐴 𝑚 𝑚$ 就是有序的方案数，显然后者比较容易划分阶段，所以我们可以算出有序的方案数再除以 $𝐴 𝑚 𝑚$ 。

然后我们发现这上面几条限制挺难同时记录并递推的，那我们可以考虑一下排除不合法方案。

设 $𝑓 𝑖$ 为选 $𝑖$ 个数的方案数，先考虑第二条限制。在这条限制下，当 $1 \sim 𝑖 - 1$ 这些数选完之后，第 $𝑖$ 个数是确定的。换句话说，满足第二条限制的方案数，即为前 $𝑖 - 1$ 个数随意选择的方案数（非空）： $𝐴 𝑖 - 1 2 𝑛 - 1$ 。

然后考虑第一条限制，发现第 $𝑖$ 个集合为空且总异或和为 $0$ ，把第 $𝑖$ 个数（空）去掉依然合法。不满足第一条限制的方案数即 $𝑓 𝑖 - 1$ 。

最后考虑第三条性质：假设第 $𝑖$ 个数与前面第 $𝑗$ 个数相同了，那么这个第 $𝑖$ 个数有 $2 𝑛 - 1 - (𝑖 - 2)$ 种取值，这个第 $𝑗$ 个数的位置有 $𝑖 - 1$ 种可能性。除此以外的地方合法（前面已经保证异或和为 $0$ 了，现在再异或两个相同的数结果不变）且长度为 $𝑖 - 2$ 。因此不满足这个要求的方案数有 $𝑓 𝑖 - 2 (2 𝑛 - 1 - (𝑖 - 2)) (𝑖 - 1)$

然后就可以递推求解了， $𝑓 𝑖 = 𝐴 𝑖 - 1 2 𝑛 - 1 - 𝑓 𝑖 - 1 - 𝑓 𝑖 - 2 (2 𝑛 - 1 - (𝑖 - 2)) (𝑖 - 1)$ ，答案是 $𝑓 𝑚$ 。

$𝐴 𝑖 - 1 2 𝑛 - 1$ 可以预处理， $𝐴 1 2 𝑛 - 1 = 2 𝑛 - 1$ ，剩下的挨个乘就好了。预处理到 $𝑚$ 即可。

CF 932 E

~~模拟赛写不动题了过来写这玩意挺合理的吧~~

原题意是给定 $| 𝕊 |, 𝑘$ ，求 $\sum 𝕋 \subseteq 𝕊 | 𝕋 | 𝑘$ 。

然后我们发现这个东西只与 $𝕊, 𝕋$ 的大小有关，所以改为枚举大小，u设 $𝑛 = 𝕊$ ，原式化为：

$𝑛 \sum 𝑖 = 1 (𝑛 𝑖) 𝑖 𝑘$

把 $𝑖 𝑘$ 用组合意义干掉。发现这玩意就是 $𝑘$ 个不同小球放进 $𝑖$ 个不同盒子的方案数。

继续组合意义分析，上面那个式子相当于是：从 $𝑛$ 个盒子里选出 $𝑖$ 个盒子，然后把 $𝑘$ 个小球放在这 $𝑖$ 个盒子里面的方案数。

~~继续发现~~发现这 $𝑘$ 个小球最多只能放满 $𝑘$ 个盒子，所以我们转头去枚举“哪些盒子有小球”。设 $𝑓 𝑖, 𝑗$ 为从 $𝑛$ 个盒子选出 $𝑗$ 个， $𝑖$ 个小球放入这 $𝑗$ 个盒子，盒子非空的方案数，然后我们要求的东西就变成了：

$𝑘 \sum 𝑖 = 1 𝑓 𝑘, 𝑖 2 𝑛 - 𝑖$

（确定 $𝑗$ 个盒子要放入小球之后，剩下 $𝑛 - 𝑗$ 个小球可能会被选入最初选的 $𝑖$ 个盒子中也有可能不被选入，所以有一个 $2 𝑛 - 𝑖$ ）。 $𝑘 ⩽ 5 \times 103$ ， $Θ (𝑘 2)$ 能过。

$𝑖$ 个小球放入 $𝑗$ 个盒子，盒子非空的方案数，相当于 $𝑖$ 个元素被划分成 $𝑗$ 个非空子集的方案数，联想到第二类斯特林数。又因为选出来的 $𝑗$ 个盒子不一定是哪几个，而且两两不同，我们还得乘进去一个排列。即 $𝑓 𝑘, 𝑖 = {𝑘 𝑖} 𝐴 𝑖 𝑛$ ，最终答案即为：

$𝑘 \sum 𝑖 = 1 {𝑘 𝑖} 𝐴 𝑖 𝑛 2 𝑛 - 𝑖$

第二类斯特林数可以 $Θ (𝑘 2)$ 预处理，递推式为 ${𝑖 𝑗} = {𝑖 - 1 𝑗 - 1} + 𝑗 {𝑖 - 1 𝑗}$ 。 $𝐴 𝑖 𝑛$ 实际上就是 $𝑛$ 的下降幂，这玩意也是直接预处理到 $𝐴 𝑘 𝑛$ 就好。后面的 $2 𝑛 - 𝑖$ 可以用快速幂或者光速幂。光速幂没啥太大必要，毕竟复杂度瓶颈不在这。

CF 1850 G

感觉这题没啥必要放，毕竟 CF 1500，但是我写的 $Θ (𝑛 l o g 𝑛)$ 大概算是常数比较小的版本吧。

发现满足要求的两个点只有四种可能： - 横坐标相等 - 纵坐标相等 - 横纵坐标和相等 - 横纵坐标差相等

所以我们把所有点按照上面四个元素作为关键字排序四次，每次分别统计相等的个数 $𝑥$ ，让答案加上 $𝑥 (𝑥 - 1)$ 就好了。

感觉比他们写的 std::map 做法常数要小。

CF 1485 F

简化题意

给定数组 $𝑏$ ，对合法的 $𝑎$ 计数。
合法的 $𝑎$ 即 $\forall 𝑖 \in [1, 𝑛], 𝑏 𝑖 = 𝑎 𝑖$ 或 $𝑏 𝑖 = \sum 𝑖 𝑗 = 1 𝑎 𝑗$

我们一个一个数填，发现对于每一个 $𝑎 𝑖$ ，有两种可能： - $𝑎 𝑖 = 𝑏 𝑖$ - $𝑎 𝑖 = 𝑏 𝑖 - \sum 𝑖 - 1 𝑗 = 1 𝑎 𝑖$

然后设 $𝑓 𝑠$ 为当前和等于 $𝑠$ 的方案数。然后上面两个可能就变成了： - $𝑓 𝑥 + 𝑏 𝑖 = 𝑓 𝑥$ - $𝑓 𝑏 𝑖 = \sum 𝑗 \in ℤ 𝑓 𝑗$

发现，第一个操作就是把整个数组向右移动了 $𝑏 𝑖$ ，所以我们只需要记录一下偏移量每次加一个 $𝑏 𝑖$ 就完成了 $Θ (1)$ 转移。

第二个实际上等于一个位置前面所有元素的和， $𝑓 𝑥$ 变成了 $𝑎 𝑛 𝑠$ ，然后原来的 $𝑓 𝑥$ 没了，于是 $𝑎 𝑛 𝑠 = 𝑎 𝑛 𝑠 - 𝑓 𝑥 + 𝑎 𝑛 𝑠$ 。

值域很大，所以要用 std::map 或者 std::unordered_map，后者需要重写哈希函数。

示例代码

cin >> n;
for (i32 i = 1; i <= n; ++ i) cin >> b[i];
f.clear();

i32 ans = f[0] = 1, delta = 0;
for (i32 i = 1; i <= n; ++ i) {
    delta += b[i];
    i32 add = (ans - f[b[i] - delta] + mod) % mod;
    f[b[i] - delta] = ans;
    ans = (ans + add) % mod;
}
cout << ans << '\n';

复制

CF 449 D

简化题意

给定数组 $𝑎$ ，从 $𝑎$ 选出非空子集使其按位与和结果为 $0$ 。求方案数

设 $𝑓 𝑠$ 为与和为 $𝑠$ 的方案数， $𝑔 𝑠$ 为与和是 $𝑠$ 的超集的方案数。

显然 $𝑓$ 做高维后缀和就得到了 $𝑔$ 。

但是发现这个 $𝑓$ 和 $𝑔$ 都不好直接求，然后发现如果设 $ℎ 𝑠$ 为数列中 $𝑠$ 的超集的数量，那么 $𝑔 𝑠 = 2 ℎ 𝑠 - 1$ （从这些超集里面随便几个取并集，显然结果一定仍然是 $𝑠$ 的超集）。

然后继续发现， $ℎ 𝑠$ 可以对 $𝑠$ 计数之后直接高位后缀和得到。

总体流程：先对 $𝑠$ 用桶计数，然后高维后缀和，然后 $𝑔 𝑠 = 2 ℎ 𝑠 - 1$ ，然后对 $𝑔$ 反着（加法变减法）做一遍高维后缀和就好了。

示例代码

i32 f[N];
i32 n;
constexpr i32 mod = 1e9+7;
constexpr i32 s = (1 << 20) - 1;

void sos(const i64& x) {
    for (i32 i = 0; i < 20; ++ i)
        for (i32 j = s; j >= 0; -- j) 
            if((j & (1 << i)) == 0)
                f[j] = (f[j] + f[j | (1 << i)] * x % mod + mod) % mod; // SOS DP
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
   
    i32 x;

    cin >> n;
    for (i32 i = 1; i <= n; ++ i) {
        cin >> x;
        ++f[x];
    }

    sos(1);
    for (i32 i = 0; i <= s; ++ i) f[i] = binpow(f[i]) - 1;
    sos(-1);

    cout << f[0];
    
    return 0;
}

复制

本文采用 GNU 自由文档许可证许可协议，转载请注明出处。