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

· · 题解

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

\mathcal{My}\ \mathcal{Blog}

传送门：染色问题 \text{[JSOI2015][P6076]}

【题目描述】

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

【分析】

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

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

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

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

$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)=\sum\limits_{i=x}^{n}\sum\limits_{j=y}^{m}\sum\limits_{k=z}^{c}C_{i}^{x}C_{j}^{y}C_{k}^{z}f(i,j,k)

由高维二项式反演可得：

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

则：

\begin{aligned}f(0,0,0)&=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}\sum\limits_{k=0}^{c}(-1)^{i+j+k-0}C_{i}^{0}C_{j}^{0}C_{c}^{0}g(i,j,k)\\&=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}\sum\limits_{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\n",ans);
}