【题解】JSOI2015染色问题

时间：2023-03-09 19:38:46
【题解】JSOI2015染色问题

　　好像这个容斥还是明显的。一共有三个要求，可以用组合数先满足一个，再用容斥解决剩下的两个维。（反正这题数据范围这么小，随便乱搞都可以）。用 \(a[k][i]\) 表示使用 \(k\) 种颜色，至少有 \(i\) 列没有染色的方案数，可以容斥预处理得到使用 \(k\) 种颜色染色使得每行每列均被染色的方案数。然后再容斥一下保证每种颜色都用上就可以了。

#include <bits/stdc++.h>

using namespace std;

#define maxn 500

#define CNST 450

#define int long long

#define mod 1000000007

int n, m, K, ans, f[maxn];

int S[maxn], C[maxn][maxn];

int read()

{

    int x = , k = ;

    char c; c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

int Qpow(int x, int timer)

{

    int base = ; if(timer < ) return ;

    for(; timer; timer >>= , x = x * x % mod)

        if(timer & ) base = base * x % mod;

    return base;

}

void Up(int &x, int y) { x = (x + y) % mod; }

void Pre()

{

    for(int i = ; i < CNST; i ++) C[i][] = ;

    for(int i = ; i < CNST; i ++)

        for(int j = ; j < CNST; j ++)

            Up(C[i][j], (C[i - ][j - ] + C[i - ][j]) % mod);

}

int Get(int X)

{

    int ret = ;

    for(int i = ; i <= m; i ++)

        S[i] = Qpow((Qpow(X + , m - i) - ), n) % mod;

    for(int i = ; i <= m; i ++)

        Up(ret, C[m][i] * ((i & ) ? -S[i] : S[i]) % mod);

    return ret;

}

signed main()

{

    n = read(), m = read(), K = read();

    Pre(); for(int i = ; i <= K; i ++) f[K - i] = Get(i);

    for(int i = ; i <= K; i ++)

        Up(ans, C[K][i] * ((i & ) ? -f[i] : f[i]) % mod);

    printf("%lld\n", (ans + mod) % mod);

    return ;

}

相关文章