题解 P6076 【[JSOI2015]染色问题】
辰星凌
2020-07-21 16:28:51
# **【题解】染色问题 [JSOI2015][P6076]**
[$\mathcal{My}\ \mathcal{Blog}$](https://www.cnblogs.com/Xing-Ling/p/13355716.html)
传送门：[染色问题 $\text{[JSOI2015][P6076]}$](https://www.luogu.com.cn/problem/P6076)
## **【题目描述】**
给出一个 $n\times m$ 的棋盘，有 $c$ 种颜色，现要对每个格子染色（可以不染），求满足每行至少有一个被染、每列至少有一个被染且每种颜色至少染了一个格子的方案数。
## **【分析】**
> 组合意义天地灭,代数推导保平安。 —— tiger0133
大家好像都是考虑容斥,咱这里有个不需要费脑子的二项式反演……（这句也是从[别人的博客里](https://www.luogu.com.cn/blog/command-block/solution-cf997c)嫖来的awa）
发现要统计的方案需满足条件“至少balabala”，不禁想到另一道题 [$\text{CF997C}$](https://www.luogu.com.cn/problem/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)=\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】**
```cpp
#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);
}
```