「JSOI2015」染色问题

传送门

sto asuldb orz

我们平时遇到的一维容斥大概长这样

$$F_{i}=\sum_{x=i}^{n}C_{x}^{i}G_{x}\Leftrightarrow G_{i}=\sum_{x=i}^{n}(-1)^{x-i}C_{x}^{i}F_{x}$$

如果说遇到高维容斥，我们只需要一维一维地解决掉即可。

但实际上，我们是可以总结出一个 $k$ 维容斥的式子的

$$F_{i_{1},i_{2},\cdots,i_{k}}=\sum_{x_{1}=i_{1}}^{n_{1}}\sum_{x_{2}=i_{2}}^{n_{2}}\cdots\sum_{x_{k}=i_{k}}^{n_{k}}\left(\prod_{j=1}^{k}C_{x_{j}}^{i_{j}}\right)G_{x_{1},x_{2},\cdots,x_{k}}\Leftrightarrow G_{i_{1},i_{2},\cdots,i_{k}}=\sum_{x_{1}=i_{1}}^{n_{1}}\sum_{x_{2}=i_{2}}^{n_{2}}\cdots\sum_{x_{k}=i_{k}}^{n_{k}}\left(\prod_{j=1}^{k}(-1)^{x_{j}-i_{j}}C_{x_{j}}^{i_{j}}\right)F_{x_{1},x_{2},\cdots,x_{k}}$$

没错，这道题就是一个三维容斥的大板子。

我们令至少 $i$ 行 $j$ 列为空，至少 $k$ 种颜色未出现的方案数为 $F_{i,j,k}$，我们有

$$F_{i,j,k}=C_{n}^{i}C_{m}^{j}C_{c}^{k}(c-k+1)^{(n-i)(m-j)}$$

话又说回来了这个东西应该是会算重啊（

恰有 $i$ 行 $j$ 列为空，恰有 $k$ 种颜色未出现的方案数为 $G_{i,j,k}$，自然

$$F_{i,j,k}=\sum_{x=i}^{n}\sum_{y=j}^{m}\sum_{z=k}^{c}C_{x}^{i}C_{y}^{j}C_{z}^{k}G_{x,y,z}$$ $$\begin{aligned} G_{i,j,k}&=\sum_{x=i}^{n}\sum_{y=j}^{m}\sum_{z=k}^{c}(-1)^{x-i+y-j+z-k}C_{x}^{i}C_{y}^{j}C_{z}^{k}F_{x,y,z}\\ &=\sum_{x=i}^{n}\sum_{y=j}^{m}\sum_{z=k}^{c}(-1)^{x-i+y-j+z-k}C_{x}^{i}C_{y}^{j}C_{z}^{k}C_{n}^{x}C_{m}^{y}C_{c}^{z}(c-z+1)^{(n-x)(m-y)}\\ &=C_{n}^{i}C_{m}^{j}C_{c}^{k}\sum_{x=i}^{n}\sum_{y=j}^{m}\sum_{z=k}^{c}(-1)^{x-i+y-j+z-k}C_{n-i}^{x-i}C_{m-j}^{y-j}C_{c-k}^{z-k}(c-z+1)^{(n-x)(m-y)}\\ &=C_{n}^{i}C_{m}^{j}C_{c}^{k}\sum_{x=0}^{n-i}\sum_{y=0}^{m-j}\sum_{z=0}^{c-k}(-1)^{x+y+z}C_{n-i}^{x}C_{m-j}^{y}C_{c-k}^{z}(c-k-z+1)^{(n-i-x)(m-j-y)}\ \end{aligned}$$

我们要求的答案就是 $G_{0,0,0}$，简单整理一下就是

$$\sum_{x=0}^{n}\sum_{y=0}^{m}\sum_{z=0}^{c}(-1)^{x+y+z}C_{n}^{x}C_{m}^{y}C_{c}^{z}(c-z+1)^{(n-x)(m-y)}$$

然后你问我为什么要写一篇 blog？闲得没事干（

代码瞎写的就不贴了（