【题解】染色问题 [JSOI2015][P6076]

传送门：染色问题 ( ext{[JSOI2015][P6076]})

【题目描述】

给出一个 (n imes m) 的棋盘，有 (c) 种颜色，现要对每个格子染色（可以不染），求满足每行至少有一个被染、每列至少有一个被染且每种颜色至少染了一个格子的方案数。

【分析】

组合意义天地灭,代数推导保平安。 —— tiger0133

大家好像都是考虑容斥,咱这里有个不需要费脑子的二项式反演……（这句也是从别人的博客里嫖来的awa）

发现要统计的方案需满足条件“至少balabala”，不禁想到另一道题 ( ext{CF997C})。类似地设 (g(i,j,k)) 表示“至少balabala”，(f(i,j,k)) 表示“恰好balabala”。
但这里的 (f,g) 都不好直接计算，而且值得注意的是，我们为了做反演而定义的“至少”与题目里的“至少”意义是不一样的。
定义的“至少”真正含义为：钦定 (k) 个满足“balabala”，其余随便。这样统计出来会有大量的重复计算。所以就算求出了 (f,g) 数组，要转换成答案还需进一步容斥。

正难则反，可以反过来设计状态：

(f(i,j,k))：恰好有 (i) 行、(j) 列一个都没染且恰好 (k) 种颜色没使用的方案数。

(g(i,j,k))：至少有 (i) 行、(j) 列一个都没染且至少 (k) 种颜色没使用的方案数。

(g(i,j,k)) 这个东西是可以直接算的，它等于 (C_{n}^{i}C_{m}^{j}C_{c}^{k}(c-k+1)^{(n-i)(m-j)}) 。

而答案为 (f(0,0,0)) 。

剩下的二项式反演就很套路了。

易知：(g(x,y,z)=sumlimits_{i=x}^{n}sumlimits_{j=y}^{m}sumlimits_{k=z}^{c}C_{i}^{x}C_{j}^{y}C_{k}^{z}f(i,j,k))

由高维二项式反演可得：

(f(x,y,z)=sumlimits_{i=x}^{n}sumlimits_{j=y}^{m}sumlimits_{k=z}^{c}(-1)^{i+j+k-x-y-z}C_{i}^{x}C_{j}^{y}C_{k}^{z}g(i,j,k))

则：
(egin{aligned}f(0,0,0)&=sumlimits_{i=0}^{n}sumlimits_{j=0}^{m}sumlimits_{k=0}^{c}(-1)^{i+j+k-0}C_{i}^{0}C_{j}^{0}C_{c}^{0}g(i,j,k)\&=sumlimits_{i=0}^{n}sumlimits_{j=0}^{m}sumlimits_{k=0}^{c}(-1)^{i+j+k}C_{n}^{i}C_{m}^{j}C_{c}^{k}(c-k+1)^{(n-i)(m-j)}end{aligned})

直接暴算复杂度 (O(nmc log_2(nm))) 比较悬，枚举的时候把 (k) 放在最外层，然后预处理 (c-k+1) 的前 (nm) 次幂，即可优化到 (O(nmc)) 。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int 
using namespace std;
const int N=403,P=1e9+7;
int n,m,K,ans,Mi[N*N],jc[N],inv[N],invjc[N];
inline void in(Re &x){
    int f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=f?-x:x;
}
inline int C(Re m,Re n){return (LL)jc[n]*invjc[m]%P*invjc[n-m]%P;}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(m),in(K),inv[1]=jc[0]=jc[1]=invjc[0]=invjc[1]=1;
    for(Re i=2;i<=max(max(n,m),K);++i)inv[i]=(LL)inv[P%i]*(P-P/i)%P,jc[i]=(LL)jc[i-1]*i%P,invjc[i]=(LL)invjc[i-1]*inv[i]%P;
    for(Re k=0;k<=K;++k){
        Mi[0]=1;
        for(Re i=1;i<=n*m;++i)Mi[i]=(LL)Mi[i-1]*(K-k+1)%P;
        for(Re i=0;i<=n;++i)
            for(Re j=0;j<=m;++j)
                (ans+=(LL)((i+j+k&1)?P-1:1)*C(i,n)%P*C(j,m)%P*C(k,K)%P*Mi[(n-i)*(m-j)]%P)%=P;
    }
    printf("%d
",ans);
}