Codeforces 844B(组合数)

Codeforces 844B
题意:给你一个$n \times m$的棋盘,上面有0、1两种棋子。同种且同行(或同列)的棋子可以形成一个集合,一个棋子也可以看做一个集合。问你最多可以有多少种集合。

考虑统计同一行或同一列的黑棋白棋,求所有行列的$\sum^{x}_{i=1} C^{i}_{x} + \sum^{x}_{i=1} C^{i}_{y}(x$为黑棋个数, $y$为白棋个数)的和,而原式可化为$2^x-1 + 2^y-1$(包括空集要减一),这样就能计算了,注意这样会多算一倍一个格子为集合的个数,减去$n \times m$即可

Codeforces Submission

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
34
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL n, m, hang[55], lie[55], c[55], ans;
void clean() {
c[0] = 1;
for (int i = 1; i <= 50; i++) c[i] = c[i - 1] * 2;
}
void solve() {
clean();
for (int i = 1; i <= n; i++)
for (int x, j = 1; j <= m; j++) {
scanf("%d", &x);
hang[i] += x, lie[j] += x;
}
ans -= n * m;
for (int i = 1; i <= n; i++) {
ans += c[hang[i]] + c[m - hang[i]] - 2;
}
for (int i = 1; i <= m; i++) {
ans += c[lie[i]] + c[n - lie[i]] - 2;
}
printf("%I64d\n", ans);
}
int main() {
scanf("%I64d%I64d", &n, &m), solve();
return 0;
}

------ 本文结束 ------