计数杂题

部分题目来自这个题单。

Luogu P6075 [JSOI 2015] 子集选取

首先，发现可以把元素单独拎出来考虑，假设对于一个元素来说有 \(x\) 种放置方案，则答案为 \(x^n\)。

继续转化题意。

对于 \(A_{i,j}\)，它必须是它左边集合的子集，也得是上边集合的子集。
也就是说，如果 \(A_{i,j}\) 包含元素 \(x\)，则在它正上方、左上方、左侧的所有集合都包含 \(x\)。（形式化来说，即 \(A_{a,b},1\leqslant a \leqslant i,1\leqslant b \leqslant j\) 均包含 \(x\)）

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

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

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

快速幂即可。

Luogu P6146 [USACO 20 FEB] Help Yourself G

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

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

1
2

---- 1  ------3
  --------- 2

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

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

考虑如何推出 \(f_i\)。

\(f_i\) 的答案由两部分组成：

• 前 \(i-1\) 个线段的答案 \(f_{i-1}\)
• 前面所有子集加上第 \(i\) 条线段的答案。

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

• 新增的连通块（复杂度）
• 除去新增，也就是原有的复杂度 \(f_{i-1}\)

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

然后问题就转化为：对前 \(i-1\) 条线段与线段 \(i\) 不相交的子集计数。
容易发现就是与线段 \(i\) 不相交的所有线段集合 \(\mathbb X\) 的子集数量，计数就是 \(2^{\lvert \mathbb X \rvert}\)

得到递推式：

\[ f_i = 2f_{i-1}+2^{\lvert \mathbb X \rvert} \]

\(\mathbb X\) 的大小我们可以预处理出来：统计每一个右端点出现的次数 \(s_i\)，然后做一个前缀和，最后 \(s_{i-1}\) 就是不覆盖点 \(i\) 的线段数量。

用快速幂优化，复杂度 \(\operatorname{O}(n\log n+n\log n)\)，如果用光速幂可以干到 \(\operatorname{O}(n\log n+n+\sqrt n)\)。

P6008 [USACO 20 JAN] Cave Paintings P

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

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

1
2
3
4
5
6

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

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

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

1
2
3
4
5
6

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

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

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

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

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

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

Luogu P1350 车的放置

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

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

具体来说，设 \(f_{i,j}\) 为前 \(i\) 行放了 \(j\) 个棋子的方案数量，则转移方程如下：

\[ f_{i,j} = f_{i-1,j} + f_{i-1,j-1} (len-j+1) \]

其中 \(len\) 是行长度。

记得把 \(f_{0\sim b+d, 0}\) 设为 \(1\)。

Luogu P3223 [HNOI 2012] 排队

基本上是纯数学题。

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

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

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

递推，设 \(f_{n,m}\) 为 \(n\) 男生 \(m\) 女生的方案数，发现推不了。

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

然后不合法方案，即两个老师靠在一起的方案，把两个老师绑在一起当一个男生求出来所有合法方案即可。别忘了两个老师顺序可以变，所以加一个 \(A^2_2\)。

最终答案：\(A^m_m A^{n+2}_{n+2} \binom{n+3}m - A^m_m A^{n+1}_{n+1}\binom {n+2}m A^2_2\)

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

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

举个例子，算 \(\binom nm\)：

1
2
3
4
5
6
7

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 家今天的饭

挺难的题。

首先我们可以把选菜看成从方阵里面选数，每行只能选一个，每列最多选 \(\lfloor \frac k2 \rfloor\) 个。

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

枚举到第 \(col\) 行，设 \(f(col)_{i,j,k}\) 为第 \(col\) 列为不合法列，前 \(i\) 行，第 \(col\) 行选了 \(j\) 个数，其他行选了 \(k\) 个数的方案数量，\(s_{i}\) 为第 \(i\) 行 \(a\) 的总和，则有转移方程：

\[ f_{i,j,k} = f_{i-1,j,k}+f_{i-1,j-1,k}\cdot a_{i,col}+f_{i-1,j,k-1}\cdot (s_i-a_{i,col}) \]

然后不合法方案数即 \(\sum_{j>k} f(col)_{n,j,k}\)

复杂度 \(\Theta(mn^3)\)，想办法减少状态。

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

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

设 \(f(col)_{i,j}\) 为第 \(col\) 列为不合法列，前 \(i\) 行，当前行选的数比别的行多 \(j\) 个的总方案数，转移方程和上面的差不多：

\[ f_{i,j} = f_{i-1,j} + f_{i,j-1}\cdot a_{i,col} + f_{i,j+1}\cdot(s_i-a_{i,col}) \]

不合法方案数：\(\sum_{j>0} f(col)_{n,j}\)

容易发现这个东西可能是负数，所以实现的时候要给 \(j\) 这一维加一个 \(n\)。

然后是计算总方案数，设 \(g_{i,j}\) 为前 \(i\) 行选了 \(j\) 个数的方案数，转移方程：

\[ g_{i,j} = g_{i-1,j} + g_{i-1,j-1} \cdot s_i \]

最终答案：\(\sum_{i=1}^n g_{n,i} - \sum_{col=1}^m\sum_{j>0}^n f(col)_{n,j}\)

Luogu P3214 [HNOI 2011] 卡农

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

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

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

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

设 \(f_i\) 为选 \(i\) 个数的方案数，先考虑第二条限制。在这条限制下，当 \(1\sim i-1\) 这些数选完之后，第 \(i\) 个数是确定的。换句话说，满足第二条限制的方案数，即为前 \(i-1\) 个数随意选择的方案数（非空）：\(A_{2^n-1}^{i-1}\)。

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

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

然后就可以递推求解了，\(f_i = A_{2^n-1}^{i-1} - f_{i-1} - f_{i-2}(2^n-1-(i-2))(i-1)\)，答案是 \(f_m\)。

\(A_{2^n-1}^{i-1}\) 可以预处理，\(A_{2^n-1}^1 = 2^n-1\)，剩下的挨个乘就好了。预处理到 \(m\) 即可。

CF 932 E

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

原题意是给定 \(\lvert \mathbb S\rvert,k\)，求 \(\sum_{\mathbb T\subseteq \mathbb S} \lvert \mathbb T \rvert ^ k\)。

然后我们发现这个东西只与 \(\mathbb {S,T}\) 的大小有关，所以改为枚举大小，u设 \(n = \mathbb S\)，原式化为：

\[ \sum_{i=1}^n \binom ni i^k \]

把 \(i^k\) 用组合意义干掉。发现这玩意就是 \(k\) 个不同小球放进 \(i\) 个不同盒子的方案数。

继续组合意义分析，上面那个式子相当于是：从 \(n\) 个盒子里选出 \(i\) 个盒子，然后把 \(k\) 个小球放在这 \(i\) 个盒子里面的方案数。

继续发现发现这 \(k\) 个小球最多只能放满 \(k\) 个盒子，所以我们转头去枚举“哪些盒子有小球”。设 \(f_{i,j}\) 为从 \(n\) 个盒子选出 \(j\) 个，\(i\) 个小球放入这 \(j\) 个盒子，盒子非空的方案数，然后我们要求的东西就变成了：

\[ \sum_{i=1}^k f_{k,i} 2^{n-i} \]

（确定 \(j\) 个盒子要放入小球之后，剩下 \(n-j\) 个小球可能会被选入最初选的 \(i\) 个盒子中也有可能不被选入，所以有一个 \(2^{n-i}\)）。\(k \leqslant 5\times 10^3\)，\(\Theta(k^2)\) 能过。

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

\[ \sum_{i=1}^k {k \brace i} A_n^i 2^{n-i} \]

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

CF 1850 G

感觉这题没啥必要放，毕竟 CF 1500，但是我写的 \(\Theta(n \log n)\) 大概算是常数比较小的版本吧。

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

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

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

CF 1485 F

我们一个一个数填，发现对于每一个 \(a_i\)，有两种可能： - \(a_i = b_i\) - \(a_i = b_i - \sum_{j=1}^{i-1}a_i\)

然后设 \(f_s\) 为当前和等于 \(s\) 的方案数。然后上面两个可能就变成了： - \(f_{x+b_i} = f_{x}\) - \(f_{b_i} = \sum_{j\in \mathbb Z} f_j\)

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

第二个实际上等于一个位置前面所有元素的和，\(f_x\) 变成了 \(ans\)，然后原来的 \(f_x\) 没了，于是 \(ans = ans - f_x + ans\)。

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

1
2
3
4
5
6
7
8
9
10
11
12

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

设 \(f_s\) 为与和为 \(s\) 的方案数，\(g_s\) 为与和是 \(s\) 的超集的方案数。

显然 \(f\) 做高维后缀和就得到了 \(g\)。

但是发现这个 \(f\) 和 \(g\) 都不好直接求，然后发现如果设 \(h_s\) 为数列中 \(s\) 的超集的数量，那么 \(g_s = 2^{h_s} - 1\)（从这些超集里面随便几个取并集，显然结果一定仍然是 \(s\) 的超集）。

然后继续发现，\(h_s\) 可以对 \(s\) 计数之后直接高位后缀和得到。

总体流程：先对 \(s\) 用桶计数，然后高维后缀和，然后 \(g_s = 2^{h_s} - 1\)，然后对 \(g\) 反着（加法变减法）做一遍高维后缀和就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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;
}