[JSOI2015] 染色问题

GitHub跳转原题关系图返回列表

把空行、空列、缺失颜色都当成坏事件做三重容斥，固定保留行列和可用颜色数后，每个剩余格子独立贡献 avail 种选择。

OJ: luogu

题目 ID: P6076

难度:提高+/省选-

标签:容斥组合计数数学推导网格

日期: 2026-06-20 08:15

目录

  1. 题意
  2. 思路
    1. 固定一个容斥状态后，剩余格子的选择数
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给定一个 n×mn \times m 棋盘，每个格子可以：

  • 不染色
  • 染成 1…c1 \dots c 中某一种颜色

要求：

  1. 每一行至少有一个格子被染色
  2. 每一列至少有一个格子被染色
  3. 每一种颜色都至少出现一次

求满足条件的方案数，对 10000000071000000007 取模。

思路

先看一个可以直接验证想法的朴素解：

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

using i64 = long long;

const i64 MOD = 1000000007LL;

int n, m, c;
int row_cnt[10], col_cnt[10], color_cnt[10];
i64 ans;

// 小数据暴力：
// 枚举每个格子是“不染色”还是染成哪一种颜色。
void dfs(int pos) {
    if (pos == n * m) {
        for (int i = 0; i < n; i++) {
            if (row_cnt[i] == 0) {
                return;
            }
        }
        for (int j = 0; j < m; j++) {
            if (col_cnt[j] == 0) {
                return;
            }
        }
        for (int k = 1; k <= c; k++) {
            if (color_cnt[k] == 0) {
                return;
            }
        }
        ans++;
        if (ans >= MOD) {
            ans -= MOD;
        }
        return;
    }

    int x = pos / m;
    int y = pos % m;

    // 不染色
    dfs(pos + 1);

    // 染成某一种颜色
    for (int color = 1; color <= c; color++) {
        row_cnt[x]++;
        col_cnt[y]++;
        color_cnt[color]++;

        dfs(pos + 1);

        row_cnt[x]--;
        col_cnt[y]--;
        color_cnt[color]--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> c;
    dfs(0);
    cout << ans << '\n';

    return 0;
}

这个暴力会逐格枚举：

  • 不染色
  • 染成某一种颜色

最后检查每一行、每一列、每一种颜色是否都满足"至少一次"。它只适合很小的数据，但能很好地说明题意。

正式做法要抓住这题最明显的信号：它有三类"至少一次"限制，分别是行、列、颜色，所以应该想到容斥原理。

固定一个容斥状态后，剩余格子的选择数

这张表描述删掉若干坏对象后的局面：

量 含义
rr 还保留了多少行
ss 还保留了多少列
avail−1avail - 1 还允许出现多少种颜色

在这个状态下，只剩 r×sr \times s 个格子还能自由选择。

而每个这样的格子有：

  • 11 种不染色
  • avail−1avail - 1 种染色方式

所以每个格子一共有 availavail 种选择，总贡献就是：

availr×savail^{r \times s}

接下来只要把三层容斥系数乘上去即可：

  • 行系数：(−1)n−r(nr)(-1)^{n-r} \binom{n}{r}
  • 列系数：(−1)m−s(ms)(-1)^{m-s} \binom{m}{s}
  • 颜色系数：(−1)c+1−avail(cc+1−avail)(-1)^{c+1-avail} \binom{c}{c+1-avail}

因此答案就是三重求和：

∑r∑s∑availrow_coef[r]×col_coef[s]×color_coef[avail]×availr×s\sum_r \sum_s \sum_{avail} row\_coef[r] \times col\_coef[s] \times color\_coef[avail] \times avail^{r \times s}

因为 n,m,c⩽400n,m,c \leqslant 400，这个三重循环是可以接受的。

代码实现里还做了一个小优化：
对固定 availavail 和 rr，把 availr×savail^{r \times s} 写成不断乘 availravail^r 的形式，这样不用在循环里反复快速幂。

代码

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

using i64 = long long;

const int MAXV = 405;
const i64 MOD = 1000000007LL;

int n, m, c;
i64 fact[MAXV], inv_fact[MAXV];
i64 row_coef[MAXV], col_coef[MAXV], color_coef[MAXV];

i64 quick_pow(i64 base, int exp) {
    i64 ans = 1;
    base %= MOD;

    while (exp > 0) {
        if (exp & 1) {
            ans = ans * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }

    return ans;
}

void init_comb(int up) {
    fact[0] = 1;
    for (int i = 1; i <= up; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    inv_fact[up] = quick_pow(fact[up], (int)MOD - 2);
    for (int i = up; i >= 1; i--) {
        inv_fact[i - 1] = inv_fact[i] * i % MOD;
    }
}

i64 C(int x, int y) {
    if (y < 0 || y > x) {
        return 0;
    }
    return fact[x] * inv_fact[y] % MOD * inv_fact[x - y] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> c;

    int up = max(n, max(m, c));
    init_comb(up);

    // row_coef[r] 表示恰好保留 r 行时的容斥系数：
    // (-1)^(n-r) * C(n,r)
    for (int r = 0; r <= n; r++) {
        row_coef[r] = C(n, r);
        if ((n - r) & 1) {
            row_coef[r] = (MOD - row_coef[r]) % MOD;
        }
    }

    for (int s = 0; s <= m; s++) {
        col_coef[s] = C(m, s);
        if ((m - s) & 1) {
            col_coef[s] = (MOD - col_coef[s]) % MOD;
        }
    }

    // avail 表示可用符号数：0(不染色) + 若干种没有被禁掉的颜色
    // 即 avail = 1..c+1
    for (int avail = 1; avail <= c + 1; avail++) {
        int miss = c + 1 - avail;
        color_coef[avail] = C(c, miss);
        if (miss & 1) {
            color_coef[avail] = (MOD - color_coef[avail]) % MOD;
        }
    }

    i64 ans = 0;

    // 三重容斥：
    // 1. 删掉若干空行
    // 2. 删掉若干空列
    // 3. 删掉若干没有出现的颜色
    //
    // 剩余 r 行 s 列时，每个格子有 avail 种选法：
    // - 不染色
    // - 染成剩下的 avail-1 种颜色之一
    //
    // 所以贡献是 avail^(r*s)
    for (int avail = 1; avail <= c + 1; avail++) {
        i64 sum_rc = 0;

        i64 pow_row = 1; // avail^r
        for (int r = 0; r <= n; r++) {
            i64 pow_cell = 1; // (avail^r)^s = avail^(r*s)
            for (int s = 0; s <= m; s++) {
                i64 add = row_coef[r] * col_coef[s] % MOD * pow_cell % MOD;
                sum_rc += add;
                if (sum_rc >= MOD) {
                    sum_rc -= MOD;
                }
                pow_cell = pow_cell * pow_row % MOD;
            }
            pow_row = pow_row * avail % MOD;
        }

        ans += color_coef[avail] * sum_rc % MOD;
        ans %= MOD;
    }

    cout << ans << '\n';

    return 0;
}

复杂度

  • 时间复杂度：O(cnm)O(cnm)
  • 空间复杂度：O(max⁡(n,m,c))O(\max(n,m,c))

总结

这题的关键不是设计复杂状态，而是认出：

  • 行至少一次
  • 列至少一次
  • 颜色至少一次

这三类限制都属于"出现性约束"，非常适合直接做容斥。

一旦固定删掉哪些行、列、颜色，剩余格子就完全独立，计数立刻变得简单。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析