CF1697E Coloring 做题记录

给定平面上的 $n$ 个点的坐标 $(x_i,y_i)$ ， 其中没有两点有相同的坐标 。定义点 $i,j$ 间的距离为 $d(i,j)=|x_i-x_j|+|y_i-y_j|$ 。

现用 $n$ 种颜色对这些点进行染色，求满足以下条件的方案数：

• 每种相同颜色的点两两间距离相等

• 每个点到具有不同颜色的点的距离总 大于 与其颜色相同的其他点（若存在）的距离。

答案取模 $998244353$ 。

$2\le n\le 100,0\le x_i,y_i\le 10^8$

一个重要的结论：

如果 $u$ 不是单独一个颜色，那么它一定与且仅与所有离它最近的点颜色相同。

证明很显然，因为每个点到具有不同颜色的点的距离需要大于与它颜色相同的点，所以与它颜色相同的点一定是离它最近的。

那么预处理出所有颜色可以相同且至少有两个点的点的集合，再设 $dp_{i,j}$ 表示前 $i$ 个集合，用了 $j$ 种颜色，转移考虑每个集合的点颜色相同或者不相同即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=105;
const int p=998244353;

struct node
{
	int x,y;
}a[S];

int n;
int C[S][S],fra[S];
int fdis[S];
vector<int> fri[S];
bool vis[S],tmp[S];
int cnt[S];
int tot,siz[S];
int dp[S][S];

inline int getdis(node x,node y)
{
	return abs(x.x-y.x)+abs(x.y-y.y);
}

int main()
{
	scanf("%d",&n);
	C[0][0]=1;
	fra[0]=1;
	for(int i=1;i<=n;i++)
	{
		fra[i]=1ll*fra[i-1]*i%p;
		C[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
		}
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	for(int i=1;i<=n;i++)
	{
		int mn=1e9;
		for(int j=1;j<=n;j++)
		{
			if(j==i)
			{
				continue;
			}
			mn=min(mn,getdis(a[i],a[j]));
		}
		fdis[i]=mn;
		for(int j=1;j<=n;j++)
		{
			if(getdis(a[i],a[j])==mn)
			{
				fri[i].push_back(j);
			}
		}
	}
	int sm=n;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			bool fl=false;
			for(int u:fri[i])
			{
				if(vis[u])
				{
					fl=true;
					break;
				}
			}
			if(fl)
			{
				continue;
			}
			int pre=fri[i].size();
			tmp[i]=true;
			cnt[i]=0;
			for(int u:fri[i])
			{
				tmp[u]=true;
				cnt[u]=1;
			}
			bool f=true;
			for(int u:fri[i])
			{
				if(fdis[u]!=fdis[i])
				{
					f=false;
					break;
				}
				for(int v:fri[u])
				{
					if(!tmp[v])
					{
						f=false;
						break;
					}
					cnt[v]++;
				}
				if(!f)
				{
					break;
				}
			}
			f&=cnt[i]==pre;
			for(int u:fri[i])
			{
				f&=cnt[u]==pre;
			}
			tmp[i]=false;
			vis[i]=f;
			for(int u:fri[i])
			{
				tmp[u]=false;
				vis[u]=f;
			}
			if(f)
			{
				siz[++tot]=pre+1;
				sm-=pre+1;
			}
		}
	}
	dp[0][0]=1;
	for(int i=1;i<=tot;i++)
	{
		for(int j=1;j<=n-sm;j++)
		{
			dp[i][j]=(1ll*dp[i-1][j-1]*j%p+(j>=siz[i]?1ll*dp[i-1][j-siz[i]]*C[j][siz[i]]%p*fra[siz[i]]%p:0))%p;
		}
	}
	int ans=0;
	for(int i=0;i<=n-sm;i++)
	{
		ans=(ans+1ll*C[n][i+sm]*C[i+sm][i]%p*dp[tot][i]%p*fra[sm]%p)%p;
	}
	printf("%d\n",ans);
	return 0;
}