题解 CF1697E 【Coloring】

Sol1 · 2022-06-14 14:07:45 · 个人记录

阴间做法自动机了属于是。

这限制看起来就非常恶心，考虑暴力。

稍微手玩一下可以得到一个感性的认知，就是同色的必须挨在一起。考虑基于感性认知进行分类讨论。

然后可以发现，对于一组同色点，它们之间距离必须两两相同并且严格小于任何一个这个颜色的点到不是这个颜色的点的距离，否则会违反限制 3。

那么我们考虑枚举出所有可能被捆起来成为同色点的点集，容易发现任意大小 \geq 2 的两个集合互不相交。如果有 S_1 和 S_2 相交，任意取 u\in S_1\cap S_2,x\in S_1,y\in S_2,x,y\neq u，那么如果 \operatorname{dis}(u,x)\leq \operatorname{dis}(u,y)，则 S_2 中 u 违反限制 3。反之 S_1 中 u 违反限制 3。从而任意两个同色点的点集互不相交。

考虑到这是二维空间曼哈顿距离，一组同色点的大小不能超过 4。

于是暴力枚举出所有可能的同色点集。这一步可以预处理出每一个点向其他点的距离最小值和最小值出现次数做到 O(n^4)，然后设分别有 M_2,M_3,M_4 个大小为 2,3,4 的可能同色。

考虑到它们互不相交，于是可以直接枚举三种集合各捆几个（暴力），再枚举捆哪些（组合数），再枚举染色方案（排列数）。得到答案为：

考虑到不交，2M_2+3M_3+4M_4\leq n，于是这一部分是 O(n^3)。

于是做完了。总复杂度 O(n^4)。跑的非常快，CF 上 31ms。

#include <bits/stdc++.h>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
    register char c = getchar();
    register int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

const long long mod = 998244353;
int x[105], y[105], n, dis[105][105], cnt[105], mnd[105];
long long fac[105], ifac[105];

inline void Read() {
    n = qread();
    for (int i = 1;i <= n;i++) {
        x[i] = qread(); y[i] = qread();
    }
}

inline void Prefix() {
    ifac[1] = 1;
    for (int i = 2;i <= n;i++) ifac[i] = (mod - mod / i) * ifac[mod % i] % mod;
    fac[0] = fac[1] = ifac[0] = 1;
    for (int i = 2;i <= n;i++) {
        fac[i] = fac[i - 1] * i % mod;
        ifac[i] = ifac[i - 1] * ifac[i] % mod;
    }
}

inline long long C(long long n, long long r) {
    if (n < r || r < 0) return 0;
    return fac[n] * ifac[r] % mod * ifac[n - r] % mod;
}

inline void Solve() {
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) dis[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]);
    }
    for (int i = 1;i <= n;i++) {
        mnd[i] = 0x3f3f3f3f;
        for (int j = 1;j <= n;j++) {
            if (j == i) continue;
            if (dis[i][j] < mnd[i]) {
                mnd[i] = dis[i][j];
                cnt[i] = 0;
            }
            if (dis[i][j] == mnd[i]) cnt[i]++;
        }
    }
    int k2cnt = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = i + 1;j <= n;j++) {
            if (dis[i][j] == mnd[i] && dis[i][j] == mnd[j] && cnt[i] == cnt[j] && cnt[j] == 1) k2cnt++;
        }
    }
    int k3cnt = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = i + 1;j <= n;j++) {
            for (int k = j + 1;k <= n;k++) {
                if (dis[i][j] == dis[j][k] && dis[j][k] == dis[k][i] && dis[i][j] == mnd[i] && dis[i][j] == mnd[j] && dis[i][j] == mnd[k] && cnt[i] == cnt[j] && cnt[j] == cnt[k] && cnt[k] == 2) k3cnt++;
            }
        }
    }
    int k4cnt = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = i + 1;j <= n;j++) {
            for (int k = j + 1;k <= n;k++) {
                for (int l = k + 1;l <= n;l++) {
                    if (dis[i][j] == dis[i][k] && dis[i][j] == dis[i][l] && dis[i][j] == dis[j][k] && dis[i][j] == dis[j][l] && dis[i][j] == dis[k][l]
                     && dis[i][j] == mnd[i] && dis[i][j] == mnd[j] && dis[i][j] == mnd[k] && dis[i][j] == mnd[l]
                     && cnt[i] == 3 && cnt[j] == 3 && cnt[k] == 3 && cnt[l] == 3) k4cnt++;
                }
            }
        }
    }
    long long ans = 0;
    for (int i = 0;i <= k2cnt;i++) {
        for (int j = 0;j <= k3cnt;j++) {
            for (int k = 0;k <= k4cnt;k++) {
                ans = (ans + C(k2cnt, i) * C(k3cnt, j) % mod * C(k4cnt, k) % mod * fac[n] % mod * ifac[i + 2 * j + 3 * k] % mod) % mod;
            }
        }
    }
    cout << ans << endl;
}

int main() {
    Read();
    Prefix();
    Solve();
    return 0;
}

当然这个做法可以进一步优化。考虑到一个点的出边最多有 3 条可以都是最小值否则不可能属于任何同色点集，于是枚举所有同色点集可以利用这个性质优化到 O(n^2)，就可以做到 O(n^3)。

当然我们还可以分析常数：

所以这题可以开到 5000！！！