Problem Link

题目大意

给定 $n\times n$ 网格，有一些格子是黑色的，每次操作可以选择一个和黑色格子相邻的白格染黑，求 $k$ 此操作能生成多少种本质不同的图案。

数据范围：$n\le 3000,k\le 4$。

思路分析

把所有格子按距离初始黑格的最短路分类，然后分讨染黑的格子的距离，容易解决 $k\le 3$ 的情况。

对于 $k=4$ 的情况，大部分都是平凡的，比较特殊的只有 $1122,1222,1223$ 三种情况，需要一定的特殊处理。

$1222$ 和 $1223$ 两种情况类似，我们分讨构成的树形态即可处理，注意特判 $\begin{bmatrix}1&2\\2&2\end{bmatrix}$ 和 $\begin{bmatrix}1&2\\2&3\end{bmatrix}$，只有这两种图形会会重复计数。

然后是 $1122$，我们先考虑两个 $2$ 分别和某个 $1$ 相邻的情况：

此时可以容斥，钦定零个或一个 $2$ 不与 $1$ 相邻可以简单计数，但钦定两个 $2$ 都不和 $1$ 相邻的问题有点困难。

设每个 $2$ 邻域中 $1$ 的集合为 $s_1\sim s_k$，$1$ 的总数为 $c$，那么所求即为 $\sum_{i<j}\binom{c-|s_i\cup s_j|}{2}$。

枚举 $i$，注意到大部分 $|s_i\cup s_j|=|s_i|+|s_j|$，又因为 $|s_i|\le 4$，因此对于每个可能的 $v\in[0,4]$，预处理 $\sum_i\binom{c-v-|s_i|}2$。

然后我们特殊处理掉 $j=i$ 以及 $s_i\cap s_j$ 非空的情况，注意到后者对应的两个点的曼哈顿距离一定 $=2$，可以直接枚举出来。

时间复杂度 $\mathcal O(n^2)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3005,MAXS=1e7+5,MOD=1e9+7,i2=(MOD+1)/2,dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char mp[MAXN][MAXN],ds[MAXN][MAXN],w[MAXN][MAXN][5];
int n,ty,m,ct[5];
vector <array<short,2>> f[5];
ll C(int x,int y) {
	if(x<0||y<0||y>x) return 0;
	__int128 p=1;
	for(int i=0;i<y;++i) p*=x-i;
	for(int i=0;i<y;++i) p/=i+1;
	return p%MOD;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>ty,memset(ds,-1,sizeof(ds));
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {
		cin>>mp[i][j],ds[i][j]=(mp[i][j]=='#'?0:5);
	}
	for(int z=1;z<=4;++z) {
		for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(ds[i][j]>z) {
			for(int k:{0,1,2,3}) {
				int x=i+dx[k],y=j+dy[k];
				if(x<1||x>n||y<1||y>n) continue;
				if(ds[x][y]==z-1) { ds[i][j]=z; break; }
			}
			if(ds[i][j]==z) {
				++ct[z],f[z].push_back({short(i),short(j)});
				for(int k:{0,1,2,3}) {
					int x=i+dx[k],y=j+dy[k];
					if(x<1||x>n||y<1||y>n) continue;
					++w[x][y][z];
				}
				
			}
		}
	}
	if(ty==1) {
		cout<<ct[1]<<"\n";
		return 0;
	}
	if(ty==2) {
		ll ans=C(ct[1],2);
		for(auto o:f[1]) ans+=w[o[0]][o[1]][2];
		cout<<ans%MOD<<"\n";
		return 0;
	}
	if(ty==3) {
		ll ans=C(ct[1],3); //111
		for(auto o:f[2]) { //112
			ans+=C(ct[1],2)-C(ct[1]-w[o[0]][o[1]][1],2);
		}
		for(auto o:f[1]) { //122 & 123
			int i=o[0],j=o[1];
			ans+=C(w[i][j][2],2);
			for(int k:{0,1,2,3}) {
				int x=i+dx[k],y=j+dy[k];
				if(x<1||x>n||y<1||y>n) continue;
				if(ds[x][y]==2) ans+=w[x][y][2]+w[x][y][3];
			}
		}
		cout<<(ans%MOD+MOD)%MOD<<"\n";
		return 0;
	}
	ll ans=C(ct[1],4); //1111
	for(auto o:f[2]) {
		int i=o[0],j=o[1];
		ans+=C(ct[1],3)-C(ct[1]-w[i][j][1],3); //1112
		ans+=(C(ct[1],2)-C(ct[1]-w[i][j][1],2))*w[i][j][3]; //1123
		//1234 & 1233
		ans+=w[i][j][1]*C(w[i][j][3],2);
		for(int k:{0,1,2,3}) {
			int x=i+dx[k],y=j+dy[k];
			if(x<1||x>n||y<1||y>n) continue;
			if(ds[x][y]==3) ans+=(w[x][y][3]+w[x][y][4])*w[i][j][1];
		}
	}
	for(auto o:f[1]) { //1222 & 1223
		int i=o[0],j=o[1],z=w[i][j][2];
		ans+=C(z,3);
		for(int k:{0,1,2,3}) {
			int x=i+dx[k],y=j+dy[k];
			if(x<1||x>n||y<1||y>n||ds[x][y]!=2) continue;
			ans+=(w[x][y][2]+w[x][y][3])*(z-1);
			ans+=C(w[x][y][2],2)+w[x][y][2]*w[x][y][3];
			for(int q:{0,1,2,3}) {
				int s=x+dx[q],t=y+dy[q];
				if(s<1||s>n||t<1||t>n) continue;
				if(ds[s][t]==2) ans+=w[s][t][2]-1+w[s][t][3];
				if(ds[s][t]==3) ans+=w[s][t][2]-1;
			}
		}
		for(int x:{i-1,i+1}) for(int y:{j-1,j+1}) if(ds[x][j]==2&&ds[i][y]==2) {
			if(ds[x][y]==2||ds[x][y]==3) ans-=3;
		}
	}
	//1122
	//link 1-2 1-2
	ans+=C(ct[1],2)*C(ct[2],2);
	ll sum[5]={0,0,0,0};
	for(int z:{0,1,2,3,4}) {
		for(auto o:f[2]) {
			int i=o[0],j=o[1];
			sum[z]+=C(ct[1]-z-w[i][j][1],2);
		}
	}
	for(auto o:f[2]) {
		int i=o[0],j=o[1],z=w[i][j][1];
		ans-=C(ct[1]-w[i][j][1],2)*(ct[2]-1);
		ll res=sum[z]-C(ct[1]-z-w[i][j][1],2);
		for(int k:{0,1,2,3}) {
			int x=i+2*dx[k],y=j+2*dy[k];
			if(x<1||x>n||y<1||y>n||ds[x][y]!=2) continue;
			if(ds[i+dx[k]][j+dy[k]]==1) {
				res-=C(ct[1]-z-w[x][y][1],2);
				res+=C(ct[1]-z-w[x][y][1]+1,2);
			}
		}
		for(int x:{i-1,i+1}) for(int y:{j-1,j+1}) if(ds[x][y]==2) {
			res-=C(ct[1]-z-w[x][y][1],2);
			res+=C(ct[1]-z-w[x][y][1]+(ds[x][j]==1)+(ds[i][y]==1),2);
		}
		ans=(ans+res%MOD*i2)%MOD;
	}
	for(auto o:f[2]) {
		//only link 2-2
		int i=o[0],j=o[1];
		for(int k:{0,1,2,3}) {
			int x=i+dx[k],y=j+dy[k];
			if(x<1||x>n||y<1||y>n||ds[x][y]!=2) continue;
			int a=w[i][j][1],b=w[x][y][1],c=ct[1]-a-b;
			ans+=C(c+a,2)-C(c,2);
		}
	}
	cout<<(ans%MOD+MOD)%MOD<<"\n";
	return 0;
}