hihocoder #1476 : 矩形计数

http://hihocoder.com/problemset/problem/1476

显然就是容斥原理了。

先算出所有的矩阵一共有多少个

    ll sum=n*(n+1)/2*m*(m+1)/2;

然后考虑对于任取x个黑色方框，

他们组成一个新的矩形，然后计算有多少个矩阵会覆盖整个矩形，也即，两条边所夹住的对顶两个小正方形的所有点的乘积

奇减偶加即可

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int N=1e5+10; ll r[15],c[22]; int main() { ll n,m; cin>>n>>m; int k; cin>>k; for(int i=0; i<k; i++) scanf("%d%d",&r[i],&c[i]); ll sum=n*(n+1)/2*m*(m+1)/2; ll all=1<<k; ll maxx,minx,maxy,miny; for(int i=1; i<all; i++) { maxx=maxy=-1e9; minx=miny=1e9; for(int j=0; j<k; j++) { if (i&(1LL<<j)) { maxx=max(maxx,r[j]); minx=min(minx,r[j]); maxy=max(maxy,c[j]); miny=min(miny,c[j]); } } ll mx=n-(maxx)+1; ll my=m-(maxy)+1; ll tmp=minx*miny*mx*my; int num=__builtin_popcount(i); if (num%2) sum-=tmp; else sum+=tmp; } printf("%lld\n",sum); return 0; }