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

· · 题解

不动脑子就可以做出来的二项式反演题。

题解

观察发现题目给出的 2,3,4 三个限制可以用以下语言表述：

二项式反演可以用来做这样一类转化：将「某种东西恰好有 x 个」的方案数转化为计算「某种东西不超过 x 个」的方案数。

首先给出二项式反演的式子：

f(n)=\sum_{i=0}^n \binom{n}{i}g(i)\iff g(n)=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}f(i)

在证明之前，我们会频繁用到二项式定理。即：

(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}

二项式反演的证明：

\begin{aligned} \sum_{i=0}^n\binom{n}{i}(-1)^{n-i}f(i)&=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}\sum_{j=0}^i\binom{i}{j}g(j)\cr &=\sum_{i=0}^n\sum_{j=0}^i\binom{n}{i}\binom{i}{j}(-1)^{n-i}g(j) \cr &=\sum_{i=0}^n\sum_{j=0}^i\binom{n}{j}\binom{n-j}{i-j}(-1)^{n-i}g(j) \cr &=\sum_{j=0}^n\binom{n}{j}g(j)\sum_{i=j}^n\binom{n-j}{i-j}(-1)^{n-i} \cr &=\sum_{j=0}^n\binom{n}{j}g(j)\sum_{i=0}^{n-j}\binom{n-j}{i}(-1)^{n-j-i} \cr &=\sum_{j=0}^n\binom{n}{j}g(j)\cdot 0^{n-j} \cr &=g(n) \end{aligned}

现在开始做这题。假设我们所求为 f(n,m,c) 为「在 n\times m 的棋盘里用 c 种颜色满足题设要求」的方案数。那么设 g(n,m,c) 为「在 n\times m 的棋盘里用不超过 c 种颜色满足其他要求（每行每列至少有一个方块上色）」，那么就有：

g(n,m,c)=\sum_{i=0}^c \binom{c}{i}f(n,m,i)\iff f(n,m,c)=\sum_{i=0}^c \binom{c}{i}(-1)^{c-i}g(n,m,i)

下面考虑计算出 g(n,m,c)。如法炮制，我们设 \varphi(n,m,c) 为「在 n\times m 的棋盘里用不超过 c 种颜色，有不超过 m 列有颜色，并且有 n 行至少有一个方块被染色」的方案数，接着是设 \psi(n,m,m) 为「在 n\times m 的棋盘里用不超过 c 种颜色，有不超过 m 列有颜色，并且有不超过 n 行有颜色」于是：

\psi(n,m,c)=\sum_{i=0}^n\binom{n}{i}\varphi(i,m,c)&\iff \varphi(n,m,c)=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}\psi(i,m,c)\end{aligned}

考虑 \psi(n,m,c) 的含义。在 n\times m 的矩形里每个格子都可以任意上色 1\sim c 内的颜色，或者该格子不上色，每个格子互不制约，由乘法原理可得：

\psi(n,m,c)=(c+1)^{nm}

于是可以推知 \varphi(n,m,c) 的表达式：

\varphi(n,m,c)=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}(c+1)^{im}=((c+1)^m-1)^n

进而得到 g(n,m,c) 的表达式：

g(n,m,c)=\sum_{i=0}^m\binom{m}{i}(-1)^{m-i}((c+1)^i-1)^n

最后得到 f(n,m,c) 的表达式：

f(n,m,c)=\sum_{i=0}^c \binom{c}{i}(-1)^{c-i}\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}((i+1)^j-1)^n

稍微整理一下：

f(n,m,c)=\sum_{i=0}^c\sum_{j=0}^m \binom{c}{i}\binom{m}{j}(-1)^{c+m-i-j}((i+1)^j-1)^n

预处理出 \binom{i}{j},i=1,2,\cdots 400,j=1,2\cdots 400，那么就可以在 \mathcal O(nm\log (nmc)) 的时间复杂度内解决该题。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
int n,m,c;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
const int MOD =1e9+7;
int pwr(int x,int y){
    int r=1; while(y){
        if(y&1) r=1ll*x*r%MOD; x=1ll*x*x%MOD,y>>=1;
    }
    return r;
}
const int MAXN=400+3;
int C[MAXN][MAXN],t=400,ans;
int main(){
    n=qread(),m=qread(),c=qread();
    up(0,t,i) C[i][i]=C[i][0]=1;
    up(1,t,i) up(1,t,j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    up(0,c,i) up(0,m,j){
        int u=1ll*C[c][i]*C[m][j]%MOD*pwr((pwr(i+1,j)-1),n)%MOD;
        if((c+m-i-j)&1) ans=(ans-u+MOD)%MOD;
        else            ans=(ans+u)%MOD;
    }
    printf("%d\n",ans);
    return 0;
}