P6076 [JSOI2015]染色问题

P6076 [JSOI2015]染色问题

我们需要求刚好使用 $C$ 个颜色且刚好 $n$ 行 $m$ 列有颜色的方案数 $f(n, m, C)$ 。

考虑先求使用不超过 $C$ 个颜色刚好 $n$ 行 $m$ 列有颜色的方案数 $g(n, m, C)$ 。那么有 $g(n, m, C) = \sum _ {i = 0} ^ C \binom C i f(n, m, i)$ ，则 $f(n, m, C) = \sum _ {i = 0} ^ C (-1) ^ {C - i} \binom C i g(n, m, i)$ 。

考虑先求使用不超过 $C$ 个颜色不超过 $n$ 行有颜色刚好 $m$ 列有颜色的方案数 $h(n, m, C)$ ，那么有 $h(n, m, C) = \sum _ {i = 0} ^ n \binom n i g(i, m, C) $ ，则 $g(n, m, C) = \sum _ {i = 0} ^ n \binom n i (-1) ^ {n - i} h(i, m ,C)$ 。

考虑先求使用不超过 $C$ 个颜色不超过 $n$ 行 $m$ 列有颜色的的方案数，即 $(C + 1) ^ {nm}$ ，那么有 $(C + 1) ^ {mn} = \sum _ {i = 0} ^ m \binom m i h(n, i, C)$ ，则 $h(n, m, C) = \sum _ {i = 0} ^ m \binom m i (-1) ^ {m - i} (C + 1) ^ {ni} = ((C + 1) ^ n -1) ^ m$ 。

那么答案为 $\sum _ {i = 0} ^ C (-1) ^ {C - i} \binom C i \sum _ {j = 0} ^ n (-1) ^ {n - j} \binom n j ((C + 1) ^ i - 1) ^ m$ 。

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        flag |= c == '-';
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x); read(y...); }
template <class Type>
void write (Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
}
typedef long long LL;
const int N = 810, mod = 1e9 + 7;
int n, m, c;
int inv[N], fact[N], ifact[N];
int binpow (int b, int k)
{
    int res = 1;
    for (; k; k >>= 1, b = (LL)b * b % mod)
        if (k & 1) res = (LL)res * b % mod;
    return res;
}
void init ()
{
    inv[1] = 1;
    for (int i = 2; i < N; ++i)
        inv[i] = -(LL)(mod / i) * inv[mod % i] % mod;
    fact[0] = ifact[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        ifact[i] = (LL)ifact[i - 1] * inv[i] % mod;
    }
}
int C (int a, int b) { return a < b ? 0 : (LL)fact[a] * ifact[b] % mod * ifact[a - b] % mod; }
int main ()
{
    init();
    read(n, m, c);
    int res = 0;
    for (int i = 0; i <= c; ++i)
        for (int j = 0; j <= m; ++j)
            (res += (c + m - i - j & 1 ? -1ll : 1ll) * C(c, i) * C(m, j) % mod * binpow(binpow(i + 1, j) - 1, n) % mod) %= mod;
    write((res + mod) % mod);
    return 0;
}