发布于 ,更新于 

计数杂题

部分题目来自这个题单

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

简化题意

给定数组 \(b\),对合法的 \(a\) 计数。
合法的 \(a\)\(\forall i \in [1,n],b_i = a_i\) 或 \(b_i = \sum_{j=1}^i a_j\)

我们一个一个数填,发现对于每一个 \(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

简化题意

给定数组 \(a\),从 \(a\) 选出非空子集使其按位与和结果为 \(0\)。求方案数

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