Luogu6076 [JSOI2015]染色问题

tony102

2021 年 10 月 07 日

2110 次浏览

暂无评论

935字数

题解

[Link](https://www.luogu.com.cn/problem/P6076)

## Sol

没有理解好这道题目，重新落实。

第一步就是要认识到，行和列可以分开计算。这道题有两个限制，一个是每种颜色至少要出现一次，而一个就是每一行和每一列都要保证有格子染色。先来处理第一个限制：颜色。

我们设 $f_i$ 表示只用了 $i$ 中颜色、并且满足行和列染色限制的方案数。我们知道：

$$
Ans = \sum\limits_{i=0}^{c} (-1)^{i} \binom{c}{i} f_{c-i}
$$

含义：从 $c$ 中选 $i$ 种颜色， 乘上只选 $c-i$  的方案数，容斥系数：$(-1)^i$

现在我们来考虑怎么求 $f_i$。我们知道 $n^{k}$ 的组合意义是将 $k$ 个小球放入 $n$ 个有区别的盒子中。那么我们可以认为每种盒子的颜色不同，每个小球上标了列标。所以总的给这一列染色（可以不染）的方案数为 $(i+1)^m$，$(i+1)$ 是因为可以不染（可以认为没染颜色是一种颜色）。因为一全空为非法，所以减 $1$ 后再进行 $n$ 次幂（有 $n$ 行，因为行之间独立）。

现在我们枚举选了多少列涂色，类似地计算：

$$
f_i = \sum\limits_{k=0}^{m} (-1)^k \binom{m}{k} ((i+1)^k-1)^n
$$

$O(n \log n)$ 计算即可。

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 4e2 + 5;
const int mod = 1e9 + 7;

int n, m, c;
int inv[SIZE], fac[SIZE], f[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

int qPow(int a, int b) {
    int ans = 1ll;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

void init() {
    const int N = 4e2;
    fac[0] = 1ll;
    for (int i = 1; i <= N; ++ i) fac[i] = fac[i - 1] * i % mod;
    inv[N] = qPow(fac[N], mod - 2ll);
    for (int i = N - 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1) % mod;
}

int C(int x, int y) {
    if (x < y) return 0ll;
    return fac[x] * inv[y] % mod * inv[x - y] % mod;
}

signed main() {
    n = read(), m = read(), c = read(); init();
    for (int i = 1; i <= c; ++ i) {
        f[i] = (qPow(i + 1, m) - 1ll + mod) % mod, f[i] = qPow(f[i], n) % mod;
        int res = 0;
        for (int k = 1; k <= m; ++ k) {
            int pw = (qPow(i + 1, m - k) - 1ll + mod) % mod; pw = qPow(pw, n) % mod;
            if ((k - 1) & 1) res = (res - (pw * C(m, k) % mod) + mod) % mod;
            else res = (res + (pw * C(m, k) % mod)) % mod;
        }
        f[i] = (f[i] - res + mod) % mod;
    }
    int ans = f[c], res = 0;
    for (int i = 1; i <= c; ++ i) {
        if ((i - 1) & 1) res = (res - (C(c, i) * f[c - i] % mod) + mod) % mod;
        else res = (res + (C(c, i) * f[c - i] % mod)) % mod;
    }
    printf("%lld\n", (ans - res + mod) % mod);
    return 0;
}
```

最后修改：2021 年 10 月 07 日