每日一题之 hiho234周 矩形计数 （容斥原理）

描述
如图所示，在由N行M列个单位正方形组成的矩形中，有K个单位正方形是黑色的，其余单位正方形是白色的。

你能统计出一共有多少个不同的子矩形是完全由白色单位正方形组成的吗？

输入
第一行三个整数:N, M和K。

之后K行每行包括两个整数R和C，代表一个黑色单位正方形的位置。

1 <= N，M <= 1000

1 <= K <= 10

1 <= R <= N

1 <= C <= M

输出
输出一个整数表示满足条件的子矩形个数。

样例输入
3 3 1
2 3
样例输出
24

思路：

这题使用容斥原理来进行计算，通过枚举i=[0,2k−1]来枚举所有不能被包含的格子的一种组合，这个组合如果包含奇数个格子，那么这一项为负数，如果包含偶数个格子（包含0个也是偶数），那么这一项为整数。

每一项的具体值如下计算：对于这些不能包含的格子，统计最左最右最上最下的位置——4个坐标，不妨设为lx,rx,ly,ry，则至少包含这些格子的方案数为lx×ly×(n−rx+1)×(m−ry+1)。

最后将所有项加在一起，就可以计算出答案。

#include <bits/stdc++.h>

using namespace std;

typedef long long llint;

const int maxn = 1e9+7;

llint mat[15][2];



void solve(int k, llint n, llint m) {

	llint res = n*(n+1)/2*m*(m+1)/2;
	for (int i = 1; i < (1<<k); ++i) { //枚举被包含的黑色矩形的个数,
		
		int num = __builtin_popcount(i);// 1的个数代表黑色矩形的个数

		llint lx = maxn;
		llint ly = maxn;
		llint rx = -1;
		llint ry = -1;

		for (int j = 0; j < k; ++j) {
			if ((1<<j) & i) {
				lx = min(lx, mat[j][0]); //最左
				ly = min(ly, mat[j][1]); //最上
				rx = max(rx, mat[j][0]); //最右
				ry = max(ry, mat[j][1]); //最下
			}
		}
		llint tmp = lx*ly*(n-rx+1)*(m-ry+1);
		if (num%2) res -= tmp;
		else 
			res += tmp;
	}

	cout << res << endl;
}

int main() {

	llint n, m, k;
	cin >> n >> m >> k;
	for (int i = 0; i < k; ++i) {
		cin >> mat[i][0] >> mat[i][1];
	}

	solve(k, n, m);

	return 0;
}