二进制枚举
引入¶
有 ${n}$ 枚硬币，正面记为 $1$，反面记为 $0$。我们想枚举所有可能的抛掷结果。
$n=3$ 时，共 $2^3=8$ 种情况:
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
for (int k = 0; k <= 1; k++)
cout << i << " " << j << " " << k << "\n";
缺点
- 循环嵌套层数与 $n$ 等价，难以扩展。
- 无法在编译期或运行期灵活支持任意 $n$。
当 $n$ 增大时
- $n=4$：需要四重循环
- $n=10$：需要十重循环，代码臃肿，易出错。
- 如何优雅地枚举任意 $n$ 枚硬币的所有情况？
这就需要学习二进制枚举！
什么是子序列？
子序列指的是：在一个序列中，按原顺序选出若干个元素（可以不连续） 形成的新序列。
例如：
若 $a = [1, 2, 3, 4]$，那么：
- $[1, 3]$
- $[1, 3, 4]$
都属于它的子序列。
示例一：硬币正反面的所有组合 = 子序列所有情况
将硬币 正面 视为被选中，反面 视为未选中，则正反面组合实际上就是对所有子序列的一种表示。
例如 $3$ 个硬币的组合：
000
001
010
011
100
101
110
111
好比有一个长度为 $3$ 的序列 $a_1,a_2,a_3$。被选中的数字用 $1$ 表示，未选中的数字用 $0$ 表示。
则以上 $8$ 种情况对应了 长度为 $3$ 的序列 $a_1,a_2,a_3$ 的所有子序列
这些组合情况也可以看作是二进制数 $000\sim 111$，因此也被称作二进制枚举。
示例二：子序列筛选问题
问题描述： 给定 $n$ 个数字，从中任意选择 $m$ 个，求有多少种方式使得这 $m$ 个数的和不超过 $k$。
分析：
- 数字可以任意选择（不要求相邻），所以是子序列问题。
- 限定子序列长度为 $m$，相当于正好选中 $m$ 个硬币正面朝上。
按照二进制的角度理解：相当于二进制数中恰好含有 $m$ 个 $1$。
前置技能¶
- 二进制 和 十进制 相互转换
- 常见位运算：按位与（
&）、或（|）、异或（^）、左移（<<）、右移（>>）、取反（~）
进制转换¶
十进制转二进制
将一个整数不断除以 $2$，记录余数，直到商为 $0$，再将余数逆序排列。
例如：十进制 $10$ 转二进制：
10 ÷ 2 = 5 ... 0
5 ÷ 2 = 2 ... 1
2 ÷ 2 = 1 ... 0
1 ÷ 2 = 0 ... 1
→ 1010（二进制）
具体实现
- 对待转换数 $n$ 做数位拆分。
- 获取
n % 2的结果即余数。 - 执行
n /= 2继续拆分。
- 获取
- 对过程中的余数保存起来，以便将来 逆序 输出。
时间复杂度：$O(\log{n})$
string s;
while (n)
{
s += n % 2 + '0';
n /= 2;
}
reverse(s.begin(), s.end()); // 逆序所有余数
二进制转十进制
将二进制每一位从右往左乘以 $2^i$ 并相加：
例如：二进制 1010 转十进制：
具体实现
- 将输入的二进制数存到字符串
s中，然后遍历字符串 $s$。 - 定义变量 $sum$ 初始化为 $0$ 保存最后的结果。
- 首先将 $sum\leftarrow sum\times 2$。相当于二进制下左移一位。
- 然后将 $sum\leftarrow sum + s[i]$。相当于二进制下加 $s[i]$ 这一位的结果。
- 注意具体实现时需要将
s[i] - ‘0’而不是用 ASCII 码。
int sum = 0;
for (char c : s)
{
sum = sum * 2 + c - '0';
}
cout << sum;
位运算¶
原码、反码、补码¶
在进行位运算前，我们需要理解计算机中数值的二进制表示方式：
1. 原码（Sign-Magnitude）
- 正数的原码就是其二进制形式。加一个符号位（最高位为 $0$）
- 负数的原码是其二进制，加一个符号位（最高位为 $1$）。
例如：
+1的原码：$\textcolor{red}00000000\ 0000000\ 00000000 \ 00000001$-1的原码：$\textcolor{red}10000000\ 0000000\ 00000000 \ 00000001$
2. 反码（Ones' Complement）
- 正数的反码与原码相同。
- 负数的反码是对其原码除符号位外的每一位取反。
例如：
+1的反码：$\textcolor{red}00000000\ 00000000\ 00000000 \ 00000001$-1的反码：$\textcolor{red}11111111\ 11111111\ 11111111 \ 11111110$
3. 补码（Two's Complement）
- 正数的补码仍与原码相同。
- 负数的补码 = 反码 $+ 1$。
例如：
+1的补码：$\textcolor{red}00000000\ 00000000\ 00000000 \ 00000001$-1的补码：$\textcolor{red}11111111\ 11111111\ 11111111 \ 11111111$
计算机中 所有数值的存储与计算 都使用 补码。
基本位运算规则¶
所有的位运算计算都是用 补码 计算。
| 运算符 | 名称 | 描述 | 示例（按位） |
|---|---|---|---|
& |
与 | 同为 $1$ 结果为 $1$ | 1101 & 1011=1001 |
| |
或 | 有 $1$ 则为 $1$ | 1101 | 1011 = 1111 |
^ |
异或 | 相同为 $0$ 不同为 $1$ | 1101 ^ 1011 = 0110 |
~ |
取反 | 所有位翻转 | ~1101 = 0010（按位） |
<< |
左移 | 所有位左移 $n$ 位，低位补 $0$ | 0001 << 2 = 0100 |
>> |
右移 | 所有位右移 $n$ 位，高位补符号位（有符号）或 $0$（无符号） | 1000 >> 2 = 0010（无符号） |
- 与运算示例
计算 10 & 4。
- 或运算示例
计算 10 | 4。
- 异或运算示例
计算 10 ^ 4。
- 左移示例
计算 10 << 2
- 右移示例
计算 10 >> 2
- 取反运算示例
计算 ~5
转回十进制原码：$-6$。
位运算的常见应用¶
我们将二进制的最低位称为第 $0$ 位，依次向高位编号至第 $n-1$ 位。
这样 第 $i$ 位 就对应数值权重 $2^i$。
- 例如二进制最低位表示 $2^0$，因此将最低位命名为第 $0$ 位。
检测二进制第 0 位 —— n & 1
直观理解:
十进制的任何任何整数 $n$ 都可以写成：
其中 $b_0$ 就是 “最低位”。
为何 n & 1 可以检测二进制第 0 位？
- 写出二者的低 $4$ 位（二进制补码）对齐对比：
& 运算只有同为 $1$ 时才得 $1$，其它均为 $0$。
-
(n & 1) == 1$\leftrightarrow b_0=1$（奇数）； -
(n & 1) == 0$\leftrightarrow b_0=0$（偶数）。
由于 奇数加偶数还是奇数，且 $2$ 的次幂只有 $2^0$ 是奇数，因此若 $n$ 二进制最后一位是 $1$，则前面的偶数会最后累加一个奇数，故而导致 $n$ 是奇数。
检测二进制第 1 位 —— n & 2
第 $1$ 位 $b_1$ 对应权重 $2^1=2$，只需和二进制 $0\ldots 0010$ 做“按位与”：
(n & 2) != 0可知 $n$ 的二进制第 $1$ 位是 $1$。- 反之二进制第 $1$ 位是 $0$。
同理检测二进制第 2 位 —— n & 4
通用检测第 $i$ 位
n & 1 << i方法
将 $1$ 左移 $i$ 位，生成二进制数 $0\ldots 01\underbrace{0\cdots0}_{i}$，与 $n$ 按位与可提取第 $i$ 位：
- 更安全写法：$\texttt{n >> i & 1}$
先将 $n$ 右移 $i$ 位，再取最低位：
无左移溢出风险，更推荐用于一般场景。
代码示例
// 检测 n 的第 0、1、2 位
if (n & 1)
cout << n << "二进制第 0 位是 1";
if (n & 2)
cout << n << "二进制第 1 位是 1";
if (n & 4)
cout << n << "二进制第 2 位是 1";
// 通用方法：检测第 i 位
for (int i = 0; i < 3; i++)
{
if (n >> i & 1) // 或写作 n & 1 << i
cout << n << "二进制第" << i << "位是 1\n";
}
统计二进制中 1 的个数
数位拆分时同步记录余数 $1$ 出现多少次即可。
- 时间复杂度：$O(\log{n})$
- 保证 $n$ 非负；若包含负数，请先取绝对值或用无符号类型。
int f(long long n)
{
int cnt = 0;
while (n > 0)
{
if (n % 2 == 1)
cnt++;
n /= 2;
}
return cnt;
}
哪些位含有 1
由于 $\texttt{long long}$ 是 $8$ 字节 $64$ 位，因此其可能的二进制位从高到低编号为
其中 $b_i$ 对应权重 $2^i$，$b_{63}$ 是符号位。
因此可枚举第 $62$ 到第 $0$ 位：for (int i = 62; i >= 0; i--)
- 对每个 $i$：计算
n >> i & 1，判断是否为 $1$。
// 输出 n 二进制中所有为 1 的位号
for (int i = 62; i >= 0; i--)
{
if (n >> i & 1)
{
cout << i << "\n";
}
}
二进制枚举概述¶
二进制枚举：枚举 $n$ 个元素“选择若干个”的所有情况。
- 对于每个元素，用二进制的「1」（选中）或「0」（不选中）来标识。
$n$ 枚硬币，每枚都有正（$1$）反（$0$）两面，组合总数为 $2^n$。
通过二进制枚举，一次性输出所有 $2^n$ 种结果：
数学知识——二进制全 “1” 的十进制含义
题型特征¶
- 特征一：问题规模小
- 一般 $n \leq 20$，因为枚举所有子集的时间复杂度是 $O(2^n)$。
- 举例：$n = 20$ 时，总共 $2^{20} \approx 10^6$，约等于 1 秒内可接受的计算量。
- 特征二：选择个数不确定
- 不像排列组合中限定选 $k$ 个，二进制枚举通常表示“选或不选”，不限定选几个。
- 特征三：子序列模型
- 给定一个数组，从中选择若干个元素（不要求连续）——这正是子序列问题的典型应用场景。
状态压缩¶
是指：使用一个整数的二进制位表示一组元素的选择状态。
举例：有 $5$ 个物品，编号从 $0$ 到 $4$。若选中编号为 $3,2,0$ 的物品，则可以用整数 $13$ 表示这种选择状态，因为：
- 每一位代表对应编号物品是否被选择，从右到左依次为编号 $0,1,\dots,n-1$。
- 例如：$i = 0$ 表示一个物品都未选，$i = 2^n - 1$ 表示所有物品都被选。
- 总共有 $2^n$ 个状态，恰好对应所有选法。
小练习：判断选中哪些物品
有 $6$ 个物品，若选择状态为 $13$ 和 $31$，各选中了哪些物品？
- $13 = 001101_2$，对应选中编号为 $3,2,0$ 的物品。
- $31 = 011111_2$，对应选中编号为 $4,3,2,1,0$。
一般的解题步骤¶
- 确定枚举状态
- 通常为 $0$ 到 $2^n - 1$，每个状态对应一种选择方案。
- 枚举所有状态
- 使用循环遍历 $0$ 到 $2^n - 1$。
- 检查状态中被选的物品
- 使用位运算判断哪些物品被选中，再进行题目所要求的处理。
通用写法：枚举所有选择状态
- 每个整数 $\texttt{mask}$（$0 \le \texttt{mask} < 2^n$）代表一种选法。
- 二进制中的每一位代表某个物品是否被选。
for (int mask = 0; mask < (1 << n); mask++)
{
// 每次循环代表一个状态
}
- 判断编号为 $i$ 的物品是否被选中
for (int i = 0; i < n; i++)
{
if (mask >> i & 1)
{
// 第 i 个物品被选中了
}
}
例题¶
模板题一¶
给定一个大小为 $n$ 的数组 $a_0, a_1, \ldots, a_{n-1}$，请你输出它的所有子集。
例如：输入 $a = {1, 2}$，输出可能为：
- 空集
- 1
- 2
- 1 2
子集枚举的基本思想
一个 $n$ 元集合的子集总共有 $2^n$ 个。
每个子集都可以用一个长度为 $n$ 的 二进制数 表示：
- 第 $i$ 位为 $1$ 表示选了 $a_i$，为 $0$ 表示没选。
所有子集对应的状态就是 $0$ 到 $2^n - 1$。
状态的二进制表示
举个例子：设 $n = 3$，数组为 $a = {10, 20, 30}$
所有子集的状态如下（用 mask 表示）：
- $000$：空集
- $001$：选了 $a_0$，即 ${10}$
- $010$：选了 $a_1$，即 ${20}$
- $011$：选了 $a_0, a_1$，即 ${10, 20}$
- $\cdots$
- $111$：全选，即 ${10, 20, 30}$
代码结构
总复杂度为 $O(n \cdot 2^n)$
for (int mask = 0; mask < (1 << n); mask++)
{
for (int i = 0; i < n; i++)
{
if (mask >> i & 1) // 如果选了 a[i]
cout << a[i] << " ";
}
cout << "\n";
}
PERKET¶
题目给出 $n$ 种食材，每种食材有两个值：酸度 $s_i$ 和 苦度 $b_i$。
你可以从中选择一个或多个食材进行搭配，计算：
- 所选食材酸度的乘积（初始为 $1$）
- 所选食材苦度的总和（初始为 $0$）
最终目标是：最小化两者的绝对差 $|S - B|$
本题没有限制选几种食材，因此是一个典型的 子集枚举问题 或者说子序列问题，即从 $n$ 个食材挑选若干个组成一个子序列。
- 每种食材可选或不选，状态数是 $2^n$
- $n \leq 10$，即 $2^{10} = 1024$，可以接受
使用二进制状态 $\texttt{mask}$ 表示一个选择方案：
- 第 $i$ 位为 $1$ 表示选择了第 $i$ 个食材
对于当前状态 mask 维护出其对应选择了哪些食材，求出酸度的乘积和苦度的和即可。
限制数量的子集¶
相比于模板题，这里要求我们：输出所有恰好选择了 $m$ 个元素的子集
- 也就是说：每个合法的选择状态，其二进制中 必须恰好有 $m$ 个 $1$
枚举所有子集的状态 $\texttt{mask}$，然后判断：
- $\texttt{mask}$ 中 恰好有 $m$ 个 $1$
- 朴素做法：实现数位拆分求二进制有几个 $1$ 的函数。
- C++ 提供了现成函数：
__builtin_popcount(mask)
满足后再输出该子集对应的元素。
选数¶
本题是在“限制数量的子集”基础上加了一层条件：
- 从 $n$ 个数中恰好选择 $k$ 个
- 选出的数字之和必须是一个质数
使用二进制枚举每一个子集，用整数 mask 表示状态：
- 若 $\texttt{mask}$ 中恰好有 $k$ 个 $1$，说明选了 $k$ 个数
- 对于每个合法的 $\texttt{mask}$，遍历它包含的元素并求和
- 检查该和是否为质数，是则计数器加一
完美的数¶
给定 $n$ 个整数，要将其划分为两组，使得：
- 两组中的数字不重复、不遗漏
这实际上是将所有数分成两个子序列，等价于选择其中一个子序列，另一个自动确定。
思路
本质上是一个子集枚举问题：
- 枚举某一个子集（记作状态 $\texttt{mask}$），代表其中一组
- 未被选中的元素自然构成另一组
- 计算两组的和，若两组和插值的绝对值小于等于 $10$，则方案数加 $1$ 即可。
总状态数为 $2^n$，$n \leq 20$ 时暴力完全可行。
kkksc03考前临时抱佛脚¶
[COCI 2015/2016 #2] GEPPETTO¶
原料个数 $N\leq 20$，因此可以枚举所有原料组合共 $2^N$ 个状态，然后一一检验当前状态是否合法即可。
枚举所有状态记作 mask，同时枚举所有冲突组合 x[i], y[i]。若 mask 二进制第 x[i] 位和第 y[i] 位是 $1$，说明当前状态不合法。
注意： 输入时将 x[i], y[i] 都减去 $1$，使得其编号从 $0$ 开始编和二进制位对应起来。
[ABC249C] Just K¶
在 $n$ 个字符串中选择任意个，这又是一个子序列模型。因为题目只在意字母出现的次数，并不在意以什么顺序组合这些字符串。
注意到 $n\leq 15$，因此枚举 $2^n$ 个所有的子序列是可行的做法。
那么接下来就是对于每一个状态 mask 首先容易求出 mask 哪些二进制位为 $1$，即当满足 mask >> i & 1 说明第 $i$ 个字符串被选了。
为了验证哪些字母恰好出现 $k$ 次，需要定义一个大小为 $26$ 的计数数组 cnt，初始化 cnt[i] = 0 代表每个字母出现 $0$ 次。
接下来当第 $i$ 个字符串被选择，我们就需要遍历这个字符串，把它里面字母的次数更新到 cnt 数组。即：
for (auto x : s[i]) cnt[x - 'a']++
最后遍历计数数组 cnt，若满足 cnt[i] == k 说明字母 $i$ 恰好出现 $k$ 次，记录恰好 $k$ 次的个数 $sum$。
结束后对 $sum$ 取 $\max$ 即可。
时间复杂度为：$O(2^n\times n\times |S|)$。其中 $|S|$ 代表字符串的长度。
[ABC167C] Skill Up¶
注意到关键是一共有 $N$ 本书，每本书要么购买要么不购买，且 $N\leq 12$，因此可以使用二进制枚举枚举所有的购买方案。
- 假设当前的购买方案的状态是
mask，假设mask二进制上 $1$ 的位置代表购买了第 $i$ 本，反之没有。
购买了第 $i$ 本书会让每个算法增加一定的能力，因此需要使用一个大小为 $M$ 的计数数组 cnt，来记录每个算法的理解水平，初始均为 $0$。
同时记录买书的花费 $sum$。
接下来遍历 cnt 数组，检验 cnt[i] 的值是否 $\geq X$，若有不满足的则当前状态 $i$ 不合法，可以打标记实现。
若当前方案合法，则对 $sum$ 求最小值即可。
实现时建议数组编号都从 $0$ 开始。
时间复杂度为 $O(2^n\times n\times m)$
[ABC128C] Switches¶
一共 $N$ 个开关，每个开关有两个状态。由于 $N\leq 10$ 因此可以枚举所有的开关组合，一共 $2^N$ 种情况。
定义一个大小为 $N$ 的标记数组 vis 记录哪个开关被开了，初始化 vis[i] = 0 代表第 $i$ 个开关是关着的。
- 那么对于每个状态
mask，若mask二进制第 $i$ 位是 $1$，即第 $i$ 个开关开了，设置vis[i] = 1即可。
接下来求出被点亮的灯泡有几个，记录为 $sum$，若满足 $sum=m$ 则说明说明灯泡都被点亮，方案数加 $1$ 即可。
- 定义 $sum=0$ 记录点亮个数。
- 枚举每个灯泡 $i$，其中 $i\in [1,m]$。
- 枚举灯泡 $i$ 连接的开关，因此在预处理存储开关的时候就要存储好，方便拿出来使用。下面给一种简单的实现方式。
vector<vector<int>> a(m + 1); // 定义 m + 1 个 vector 保存每一个灯泡连接的开关
for (int i = 1; i <= m; i++)
{
int k;
cin >> k;
for (int j = 1; j <= k; j++)
{
int x;
cin >> x;
x--; // 让 x - 1 的目的是让开关的编号从 0 开始，因为二进制枚举的状态 i 是开关的状态。
a[i].push_back(x);
}
}
- 接下来对于当前第 $i$ 个灯泡的开关就可以通过
for (auto x : a[i]来遍历。 - 此时若
vis[x] == 1说明 $x$ 这个开关被开了，记录开的总个数 $num$。 - 遍历结束后，若
num % 2 == p[i]说明这个灯泡被点亮了，执行sum++即可。 - 若
sum == m说明当前状态 $i$ 可行，ans++即可。
[ABC197C] ORXOR¶
长度为 $n$ 的序列划分为若干个非空子段。可以看作是在若干个位置进行断开，那么一共有 $n$ 个位置可以断开，因此最多 $2^n$ 种划分方案。由于 $n\leq 10$因此可以枚举所有的情况。
接下来记录到底哪些位置是分断点，即 for (int i = 0; i < n; i++) if (mask >> i & 1)，此时 $i$ 就是一个断点。
我们需要记录上一个断点位置 last 初始化为 $0$，那么当前这一段就是 $last\sim i$，遍历这个范围求出或的结果。在和总异或值进行异或即可。
注意有一个隐藏的断点，即 $n$ 这个位置，也就是最后剩余一些元素也要计算一次。需要单独计算一次。
时间复杂度为 $O(2^n\times n\times n)$。
[CSP-S 2024] 染色¶
只做前 $20$ 分即可，注意到 $20$ 分的范围中，$n\leq 15$，且每个位置要么染色红色要么染色蓝色，是一个二选一的行为，因此可以使用二进制枚举枚举所有的染色方案，定义 $1$ 代表红色，$0$ 代表蓝色即可。
在具体实现中，对于每个状态 $i$，首先定义两个数组 $c$ 长度为 $n$ 记录红色和蓝色的位置。
vector<int> c(n);
for (int i = 0; i < n; i++)
{
if (mask >> i & 1)
c[i] = 1; // 第 i 个位置是红色
else
c[i] = 0; // 第 i 个位置是蓝色
}
接下来使用两个变量 $last1,last2$ 分别记录上一个红色和蓝色的位置。那么就可以遍历整个数组来计算得分了。
int last1 = -1, last2 = -1; // 初始化为 -1 代表上一个颜色位置不存在
int sum = 0;
for (int i = 0; i < n; i++)
{
if (c[i] == 1) // 如果是红色
{
if (last1 != -1 && a[last1] == a[i]) // 上一个红色位置存在且数值还相同
sum += a[i];
last1 = i; // 更新红色位置
}
else
{
if (last2 != -1 && a[last2] == a[i])
sum += a[i];
last2 = i;
}
}
mx = max(mx, sum);
注意本题多组数据。
寻找团伙¶
注意到 $n$ 个人随便挑一些出来，且 $n\leq 21$ 因此不难想到使用二进制枚举，枚举所有的挑选方案求解最大值。
注意到题目说一个能力如果被选了偶数次，则不参与计算。因此对于每个状态 $i$ 应该定义一个大小为 $k+1$ 的数组 cnt 统计每个能力被选了多少次。初始化 cnt[i] = 0。
这个题输入和前面某一题类似，可以用 vector 便捷实现。注意编号从 $0$ 开始输入，因为人的编号是我们二进制枚举用的，所以人的编号需要从 $0$ 开始和二进制位一一对应。
vector<vector<int>> a(n);
for (int i = 0; i < n; i++)
{
int c;
cin >> c;
for (int j = 1; j <= c; j++)
{
int x;
cin >> x;
a[i].push_back(x);
}
}
接下来对于每一个状态 $i$ 首先求出每个能力被选的次数。
vector<int> cnt(k + 1, 0);
for (int i = 0; i < n; i++)
if (mask >> i & 1)
for (auto x : a[i]) // 遍历 a[i] 这个人的所有能力 x
cnt[x]++;
接下来枚举每一个能力值 $i$，其中 $i\in [1,k]$，若 cnt[i] % 2 == 1。说明这个能力可以使用，那么累加它的能力值即可，注意要乘以对应的权重，第 $j$ 个的权重就是 $2^{k-i}$。
long long sum = 0;
for (int i = 1; i <= k; i++)
{
if (cnt[i] & 1)
{
sum += 1ll << (k - i); // 用位运算快速实现 2 的 次幂
}
}
ans = max(ans, sum);
涂色¶
首先可以把行和列分开处理，本题也是子序列模型，即在行 $\sim n$ 中挑选若干个数字，在列 $1\sim m$ 中挑选若干个数字。
由于 $n,m\leq 6$，那么枚举行和列的所有组合就是 $2^n\times 2^m$，不会超时。 注意首先行和列的情况是互相组合的，因此需要循环嵌套的枚举。
for (int i = 0; i < 1 << n; i++) // 枚举行的状态
for (int j = 0; j < 1 << m; j++) // 枚举列的状态
假设二进制位里值为 $1$ 代表这一行或这一列没有被去掉。我们需要做的就是在剩下的行和列组合的矩阵中求出字符 # 的个数，是否恰好等于 $K$，因此如何求出剩余的字符 # 个数是本题的关键所在。
要解决这个问题，我们就需要继续遍历到底是哪些行和哪些列被留下了。
for (int x = 0; x < n; x++)
for (int y = 0; y < m; y++)
此时若满足 i >> x & 1 and j >> y & 1 说明第 $x$ 行第 $y$ 列这个格子被留下了。
假设原始输入的矩阵是 $a$，此时若满足 a[x][y] == '#'，则计数变量加 $1$ 即可。
循环结束后验证计数变量的值是否恰好等于 $K$，若等于则方案数加 $1$。 时间复杂度为 $O(2^n\times 2^m\times n\times m)$。