P9629 [ICPC2020 Nanjing R] Harmonious Rectangle 题解

运用小学学过的鸽巢原理推断一下，当 \(\max(n, m)>9\) 的时候，由于我们只有三种颜色，任何染色方案都是合法的。染色方案数是 \(3^{nm}\)。

再来考虑 \(\max(n,m)\le 9\) 的情况，合法染色方案数就是所有方案数减去不合法的方案数。

当然就八十几个情况，你要打表也是可以哒！这里我直接写了个搜。

#define rep(l, x, a, b) for (l x = a, x##END = b; x <= x##END; ++x)
using ll = long long;
// 三种颜色分别是 1、2、3
constexpr static ll N = 1e4 + 114, Mod = 1e9 + 7;
ll me[N][N];
int T, n, m;
ll ans;
int col[N][N];
int sel[4][N]; // 由于我们搜的是列，同时还需要考虑行的情况，sel[i][x] 表示第 x 行有多少个 i 颜色
bool ok(int x, int y, int d) {
    col[x][y] = d;
    if(sel[1][x] <= 3 && sel[2][x] <= 3 && sel[3][x] <= 3) {
        rep(int, i, 1, x - 1)
            rep(int, j, 1, y - 1) { // 根据题目的约束条件检查
                int d_ = col[i][j];
                if((d == col[i][y] && d_ == col[x][j])
                ||(d == col[x][j] && d_ == col[i][y])) return 0;
            }
        return 1;
    }
    return 0;
}
void dfs(int x, int y) {
    if(x > n) { // 搜完了记到 ans 里面
        ++ans;
        return;
    }
    if(y > m) { // 这一列可以了，考虑下一列
        dfs(++x, 1);
        return;
    }
    rep(int, i, 1, 3) {
        ++sel[i][x];
        if(ok(x, y, i)) // 继续搜
            dfs(x, y+1);
        --sel[i][x]; // 回溯掉
    }
}
void solve() {
    for(std::cin >> T; T--; [&](){
        std::cin >> n >> m;
        if(n > m) std::swap(n, m); // 优化小技巧
        if(me[n][m]) return std::cout << me[n][m] << '\n', void(); // 优化小技巧
        if(n == 1 || m == 1) return std::cout << 0 << '\n', void(); // 判掉只有一行或一列的情况
        if(n > 9 || m > 9) return std::cout << fpow(3ll, n*m, Mod) << '\n', void();
        ans = 0;
        dfs(1, 1);
        std::cout << (me[n][m] = (fpow(3ll, n*m, Mod) - ans + Mod) % Mod) << '\n'; // 所有情况去掉不合法情况
    }());
}

P9629 [ICPC2020 Nanjing R] Harmonious Rectangle 题解

评论