Snake Rana Gym - 101350G
https://cn.vjudge.net/contest/303719#problem/B
题目大意：给定一个矩阵，和矩阵中的一些点，求矩阵中不包含这些点的子矩阵的数量
容斥原理：并集 = 总情况 - 两个集合相交的情况情况 + 三个集合相交的情况 - 四个集合相交的情况 +五个集合相交的情况 ……(依次类推)
#include <stdio.h> #include <iostream> using namespace std; #define inf 1e9 const int maxn = 1e5+100; struct p { long long x,y; } a[maxn];//记录点的坐标 int main() { int T; scanf("%d",&T); while (T--) { long long m,n,k; scanf("%lld%lld%lld",&n,&m,&k); for (int i=0; i<k; i++) { scanf("%lld%lld",&a[i].x,&a[i].y); } long long ans=(n+1)*n/2*(m+1)*m/2;//矩阵包含的子矩阵数量，Cn2*Cm2(行列各取两条边，构成子矩阵) for (int s=1; s<(1<<k); s++)//总共有k个点，有2^n-1种集合相交的情况,所以用二进制模拟点的存在情况（0代表不存在，1代表存在）（这里是从1到 2^n-1,没有0,因为至少要有一个点，至多k个点，也就是2^n-1） { long long minx=inf,miny=inf,maxx=-1,maxy=-1; int cnt=0; for (int i=0; i<k; i++)//对于每种情况，求出包含这些点的最小的矩阵 { if (s>>i&1)//如果在这种情况下，包含此点（此位的二进制是1） { minx=min(minx,a[i].x); miny=min(miny,a[i].y); maxx=max(maxx,a[i].x); maxy=max(maxy,a[i].y);//得到矩阵范围 cnt++;//记录这种情况下包含点的个数 } } long long res=minx*miny*(n-maxx+1)*(m-maxy+1);//求出交集，即横坐标在最小矩阵范围上（minx）下(n-maxx+1)各取两条线，有minx*(n-maxx+1)种情况；纵坐标在最小矩阵范围左（miny）右(m-maxy+1)各取两条线，有miny*(m-maxy+1)种情况，两者相乘即为总情况 if (cnt&1)//如果点的个数是奇数，就减去 ans-=res; else//如果点的个数是偶数，就加上 ans+=res; } printf("%lld\n",ans); } }
