P8915 题解

· · 题解

是一血的题解捏（

思路

## $k=2

先考虑 k=2，也就是问有多少两个的不相邻的。这种不好统计，考虑去统计总数减去相邻的。

总数

先考虑总数，共有 n\times m-t 个可占用格子，故答案为 \dbinom{n\times m-t}{2}。

相邻

没有黑格子情况下，相邻的共有 n\times (m-1)+m\times (n-1) 个，即每个 1\times 2 的小格子。有黑格子呢？对于每个黑格子，添加进来后与周围白格子都构成一组不符合要求的相邻组，故扣减即可。

答案

设相邻的有 cnt 个，故答案为 \dbinom{n\times m-t}{2}-cnt。

k=3

前面相邻的还有有用的，我们还是考虑容斥计算，总数减去钦定两个相邻，再加上三个都相邻的。

总数

容易发现是 \dbinom{n\times m-t}{3}。

相邻

首先每个 2\times 2 正方形内包含 4 个连通的，每个 1\times 3 中包含 1 个，故总共有 (n-2)\times(m-2)\times4+(n-3)\times(m-1)+(n-1)\times(m-3) 个。

然后对于每个黑格子，他会在 6 种 3 连通块中的每个位置，故 18 种情况依次枚举扣减即可。

答案

设 2 相邻有 cnt_1 个，3 相邻有 cnt_2 个，故答案为 \dbinom{n\times m-t}{3}-cnt_1\times(n\times m-t-2)+cnt_2。

总结

大力分讨+一定思维含量的推式子以及容斥。

坑点

首先在计算的时候所有减法一定要和 0 取 \max。

然后就是经典问题，一定记得取模！

代码

#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r+1)>>1)
using namespace std;
const int mod=1e9+7;
const int mul=1e9+2;
int n,m,k,t;
map<int,int> mp;
bool ok(int x,int y){
    if(x<1||y<1||x>n||y>m) return false;
    if(mp[x*mul+y]) return false;
    return true;
}
signed main(){
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m>>k>>t;
        mp.clear();
        int nr=n*(m-1)+(n-1)*m,nr2=(n-1)*(m-1)*4+n*max(0ll,m-2)+m*max(0ll,n-2);
        for(int i=1;i<=t;i++){
            int x,y;
            cin>>x>>y;
            if(ok(x-1,y)) nr--;
            if(ok(x+1,y)) nr--;
            if(ok(x,y-1)) nr--;
            if(ok(x,y+1)) nr--;
            if(ok(x+1,y)&&ok(x,y+1)) nr2--;
            if(ok(x+1,y)&&ok(x,y-1)) nr2--;
            if(ok(x-1,y)&&ok(x,y+1)) nr2--;
            if(ok(x-1,y)&&ok(x,y-1)) nr2--;
            if(ok(x+1,y)&&ok(x+1,y+1)) nr2--;
            if(ok(x+1,y)&&ok(x+1,y-1)) nr2--;
            if(ok(x-1,y)&&ok(x-1,y+1)) nr2--;
            if(ok(x-1,y)&&ok(x-1,y-1)) nr2--;
            if(ok(x,y+1)&&ok(x-1,y+1)) nr2--;
            if(ok(x,y+1)&&ok(x+1,y+1)) nr2--;
            if(ok(x,y-1)&&ok(x-1,y-1)) nr2--;
            if(ok(x,y-1)&&ok(x+1,y-1)) nr2--;
            if(ok(x+1,y)&&ok(x-1,y)) nr2--;
            if(ok(x,y+1)&&ok(x,y-1)) nr2--;
            if(ok(x+1,y)&&ok(x+2,y)) nr2--;
            if(ok(x-1,y)&&ok(x-2,y)) nr2--;
            if(ok(x,y+1)&&ok(x,y+2)) nr2--;
            if(ok(x,y-1)&&ok(x,y-2)) nr2--;
            mp[x*mul+y]=1;
        }
        nr%=mod,nr2%=mod;
        int tot=(n*m-t)%mod;
        int num2=(tot*(tot-1)/2)%mod;
        int num3=(tot*(tot-1)%mod*(tot-2)%mod*166666668)%mod;
        if(k==2) cout<<(num2+mod-nr)%mod<<endl;
        else cout<<(num3+mod-nr*max(tot-2,0ll)%mod+nr2)%mod<<endl;
    }
    return 0;
}