自动搬运

查看原文

来自洛谷，原作者为

	dAniel_lele 当你在幻想上天会给你开一扇窗的时候，你已经输一半了。

搬运于2025-08-24 22:43:42，当前版本为作者最后更新于2022-12-24 21:06:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

是一血的题解捏（

思路

$k$ 很小，一定是突破口。

$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;
}