给定平面上的 个点的坐标 , 其中没有两点有相同的坐标 。定义点 间的距离为 。
现用 种颜色对这些点进行染色,求满足以下条件的方案数:
每种相同颜色的点两两间距离相等
每个点到具有不同颜色的点的距离总 大于 与其颜色相同的其他点(若存在)的距离。
答案取模 。
一个重要的结论:
如果 不是单独一个颜色,那么它一定与且仅与所有离它最近的点颜色相同。
证明很显然,因为每个点到具有不同颜色的点的距离需要大于与它颜色相同的点,所以与它颜色相同的点一定是离它最近的。
那么预处理出所有颜色可以相同且至少有两个点的点的集合,再设 表示前 个集合,用了 种颜色,转移考虑每个集合的点颜色相同或者不相同即可。
代码如下:
#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;
}