CF1697E Coloring 题解

· · 题解

从条件入手，考虑如果两个点可以染成同色会是什么情况。

根据第二条限制，不难发现点对 (x,y) 可以染成同色时 x,y 互为对方距离最近的点。

但最近的点可能有多个，第一条限制告诉我们这时应该把这些点放在一起，但这样的连通块不一定是合法的，加入一个点时需要满足已经加入的点全部是新加入点的最近点才能染成同一种颜色。

显然可以染成同色的点被分成了若干互不相交的连通块，那么我们可以预处理出来每个点的最近点集合，然后从每个点开始 dfs，记点 i 的距离最近点的距离是 minn_i，那么我们 dfs 时只访问 minn_j=minn_i 的相邻点，把这样的点加入连通块中，并且判断这个连通块是否合法即可。如果合法，我们用并查集把他们连起来，表示这些点要么两两不同色，要么全部同色。

接下来考虑怎样计算答案，记 dp_i 表示用 i 种颜色讲整个图染色的合法方案数，那么这就是一个简单 01 背包，每个连通块看做一个物品，可以产生连通块大小或 1 的贡献，这样做完背包之后答案就是 \sum\limits_{i=1}^nn^{\underline i}dp_i，其中 n^{\underline i}=\prod\limits_{j=1}^in-j+1。

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

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int mod=998244353;
int n,minn[101],bin[101],s[101],dp[101],f[101],fac[101],inv[101],ans;
pair<int,int> a[101];
vector<int> v[101],tmp;
bool vis[101],flag;
inline int pw(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
            res=1ll*res*a%mod;
        b>>=1;
        a=1ll*a*a%mod;
    }
    return res;
}
inline int anc(int k)
{
    if(!bin[k])
        return k;
    return bin[k]=anc(bin[k]);
}
inline void link(int x,int y)
{
    x=anc(x);
    y=anc(y);
    if(x^y)
    {
        bin[y]=x;
        s[x]+=s[y];
    }
}
inline int dis(int x,int y)
{
    return abs(a[x].first-a[y].first)+abs(a[x].second-a[y].second);
}
inline void dfs(int k,int val)
{
    tmp.emplace_back(k);
    vis[k]=1;
    for(int i:v[k])
    {
        if(minn[i]<val)
            flag=0;
        if(vis[i])
            continue;
        for(auto j:tmp)
            if(find(v[i].begin(),v[i].end(),j)==v[i].end())
            {
                flag=0;
                break;
            }
        if(minn[i]==val)
            dfs(i,val);
    }
}
inline int c(int x,int y)
{
    return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
    cin>>n;
    fac[0]=inv[0]=1;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i].first>>a[i].second;
        s[i]=1;
        fac[i]=1ll*fac[i-1]*i%mod;
    }
    inv[n]=pw(fac[n],mod-2);
    for(int i=n-1;i>=1;--i)
        inv[i]=1ll*inv[i+1]*(i+1)%mod;
    for(int i=1;i<=n;++i)
    {
        minn[i]=1e9;
        for(int j=1;j<=n;++j)
            if(i!=j)
            {
                int val=dis(i,j);
                if(val<minn[i])
                {
                    minn[i]=val;
                    v[i].clear();
                    v[i].emplace_back(j);
                }
                else if(val==minn[i])
                    v[i].emplace_back(j);
            }
    }
    for(int i=1;i<=n;++i)
        if(!vis[i])
        {
            tmp.clear();
            flag=1;
            dfs(i,minn[i]);
            if(flag)
                for(auto j:tmp)
                    link(i,j);
        }
    dp[0]=1;
    for(int i=1;i<=n;++i)
        if(anc(i)==i)
        {
            for(int j=0;j<=n;++j)
            {
                f[j]=dp[j];
                dp[j]=0;
            }
            for(int j=n;j>=s[i];--j)
                dp[j]=(dp[j]+f[j-s[i]])%mod;
            if(s[i]^1)
                for(int j=n;j>=1;--j)
                    dp[j]=(dp[j]+f[j-1])%mod;
        }
    for(int i=1;i<=n;++i)
        ans=(ans+1ll*c(n,i)*fac[i]%mod*dp[i]%mod)%mod;
    cout<<ans<<'\n';
    return 0;
}