atabc173c C - H and V

此题目主要包括了全排列，二进制的相关知识

C - H and V(单击题目可进入下图链接)

题意：第一次看的时候，看的有点呆。

给定一个矩阵，每个点都被标记为白色或者黑色，然后使你开始刷漆（红漆），一次可以涂一行或者一列，任意涂刷n次（可以是0）求有多少种方案可以使得最终黑色的砖块的数量为所给的数量。

当时思考：

opps，不会吧，难道是要暴力？这个怎么暴力？这不可能暴力吧，这么复杂呢。第一行可刷可不刷，第一列可刷可不刷。那么岂不是有很多的情况么，怎么处理呢。当场傻掉。

题解：

暴力~~~（逃不过）

但是采用了和二进制映射map的操作，也就是说 对于每一行我们有两个状态，涂刷或者不涂刷，那么一共有 h 行，w列。行的变化之间是互不关联的，所以说一共有 $2^h$ 种可能，同理 列也有 $2^w$ 种可能的情况，他们都是独立的，所以该涂刷方案一共有 $2^h * 2^w = 2^{(h+w)}$ 种可能的涂刷方案2333.

注意到数据的范围： 1≤H,W≤6 所以 如果采暴力的方法我们也不过是 $2^{12} = 4096$ 次操作，并不会从boom，是一个相对计算机而言很小的一个数据大小。

那么如何去储存一个 4096（最大） 种情况呢（其中每一种情况要表示：一共要涂刷的行或者列），我们采用了二进制状态映射的方法（回想之前全排列的二进制方法） 同样这次我们对于 矩阵的行 而言，一共有h行，那么一共有 $2^h$ 种行的不同状态（即不同的涂刷方式）我们就采取二进制的方法记录，这种对于单个单位（如 此处的行）只有两种状态的数据的存储。例如：0b001 可以表示第一行第二行不刷红色，第三行刷红。

我们采用 0 表示不涂刷，或者表示涂刷都是可以的，无伤大雅（毕竟有一个不刷的状态就会有刷的情况与之对应，我们将全部情况都列出来了 了 了）。所以 十进制下的 $0-(h-1)$ 就可以将 $2^h$ 种状态全部表示出来了。

如果我们采用的是其他（比如，采用了 用一个矩阵来保存一种可能性的结果的话，那么就需要4000多个矩阵来表示，但想想一个矩阵我们采用一个二维数组emm 过于复杂咯，更何况每个矩阵依旧是需要依次遍历循环 判断黑色个数）

同理，我们也可以将列的表示如上方式，这样我们就实现了：采用一个十进制的数字（其实需要的是它所对应的二进制），来表示一行或者一列的涂刷情况了。

接着，我们就要判断出该行列状态下的黑砖的数量是不是和题目要求的一致，一致就cnt++。

具体实现：

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
	int H, W, K;
	scanf("%d %d %d", &H, &W, &K);
	char c[H][W];
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) scanf(" %c", &c[i][j]);
	}
	int ans = 0;

	for (int i = 0; i < (1 << H); ++i) {
		for (int j = 0; j < (1 << W); ++j) {
			int cnt = 0;
			// above is the every situation that we may face

			// for each block c[k][l]
			for (int k = 0; k < H; ++k) {
				for (int l = 0; l < W; ++l) {
					//i , j = 0b0101 
					if (!(i & (1 << k)) && !(j & (1 << l)) && c[k][l] == '#') ++cnt;//1 red, 0 not red
					
					//if ((i & (1 << k)) && (j & (1 << l)) && c[k][l] == '#') ++cnt;//0 red, 1 not red
				}
			}
			if (cnt == K) ++ans;
		}
	}
	printf("%d", ans);
	return 0;
}