[hiho1476]-矩形计数-简单容斥

说在前面

本来是想做 计数类dp的（大概是…连通图计数之类的东西）
然后找到了这个题= =？？？
天天刷水题

---

题目

hiho1476传送门（需要登录才能看emmmm）

题目大意

给出一个N∗M$N\ast M$的方格图，其中有K$K$个格子是黑色的
询问不包含黑色格子的子矩形有多少个
其中N,M≤1000$N,M\le 1000$，K≤10$K\le 10$

如图样例为24

输入输出格式

输入格式：
第一行三个整数N,M,K$N,M,K$，含义如题
接下来K行，每行两个数字l,c$l,c$表示所在行列

输出格式：
输出一个整数表示答案

---

解法

K$K$这么小对不对！
直接容斥就好了=w=
（注意到不同情况可能有包含关系，但是这样容斥也是ok的）

---

下面是代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

int N , M , K , inf = 0x3f3f3f3f ;
struct Point{
    int x , y ;
} p[15] ;

void solve(){
    long long ans = 1LL * ( M * N ) * ( M * N ) ;//任意撒两个点
    ans += 1LL * N * M * M ;//同一行
    ans += 1LL * M * N * N ;//同一列
    ans += N * M ;//同一点
    ans >>= 2 ;//矩形总数

    int Fstate = ( 1 << K ) - 1 ;
    for( int i = 1 ; i <= Fstate ; i ++ ){
        long long fix = ( __builtin_popcount( i ) & 1 ? -1 : 1 ) ;
        int mnx = inf , mny = inf , mxx = 0 , mxy = 0 ;
        for( int j = 1 ; j <= K ; j ++ ) if( i & ( 1 << ( j - 1 ) ) ){
            mnx = min( mnx , p[j].x ) ;
            mny = min( mny , p[j].y ) ;
            mxx = max( mxx , p[j].x ) ;
            mxy = max( mxy , p[j].y ) ;
        }
        ans += fix * mnx * mny * ( N - mxx + 1 ) * ( N - mxy + 1 ) ;
    } printf( "%lld" , ans ) ;
}

int main(){
    scanf( "%d%d%d" , &N , &M , &K ) ;
    for( int i = 1 ; i <= K ; i ++ )
        scanf( "%d%d" , &p[i].x , &p[i].y ) ;
    solve() ;
}