题目
看到这个限制条件有点多，我们就一直容斥好了
先容斥颜色，我们枚举至少不用\(i\)种颜色
再容斥列，我们枚举至少不用\(j\)列
最后容斥行，枚举至少不用\(k\)行
容斥系数显然是\((-1)^i,(-1)^j,(-1)^k\)，我们从\(c\)种颜色里选出\(i\)种不用，\(m\)列里选出\(j\)列不凃，\(n\)行里选出\(k\)行不凃，分别是\(\binom{c}{i},\binom{m}{j},\binom{n}{k}\)
对于剩下的\((m-j)(n-k)\)个格子，每个格子我们有\(c-i\)种颜色可以涂，或者直接空着，所以有\(c-i+1\)种选择
于是我们的答案就是
\[\sum_{i=0}^c\sum_{j=0}^m\sum_{k=0}^n(-1)^{i+j+k}\binom{c}{i}\binom{m}{j}\binom{n}{k}\times (c-i+1)^{(m-j)(n-k)}\]
里面用快速幂算那个东西会\(T\)的，我们乱搞一下就能优化成\(O(nmc)\)了
代码
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define re register#define LL long longinline int read() { ???char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar(); ???while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const int mod=1e9+7;const int maxn=405;int n,m,c;int fac[maxn],inv[maxn],ifac[maxn];inline int C(int n,int m) { ???if(m>n) return 0; ???return 1ll*fac[n]*ifac[n-m]%mod*ifac[m]%mod;}inline int ksm(int a,int b) { ???int S=1; ???while(b) {if(b&1) S=1ll*S*a%mod;b>>=1;a=1ll*a*a%mod;} ???return S;}int main() { ???n=read(),m=read(),c=read(); ???inv[1]=1,fac[0]=1,ifac[0]=1; ???for(re int i=1;i<=400;i++) fac[i]=1ll*fac[i-1]*i%mod; ???for(re int i=2;i<=400;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; ???for(re int i=1;i<=400;i++) ifac[i]=1ll*ifac[i-1]*inv[i]%mod; ???int ans=0; ???for(re int i=0;i<=c;i++) ???????for(re int j=0;j<=m;j++) { ???????????int now=1,t=ksm(c-i+1,m-j); ???????????for(re int k=n;k>=0;--k) { ???????????????int tot=1ll*C(c,i)*C(m,j)%mod*C(n,k)%mod*now%mod; ???????????????if((i+j+k)&1) ans=(ans-tot+mod)%mod; ???????????????????else ans=(ans+tot)%mod; ???????????????now=1ll*now*t%mod; ???????????} ???????} ???printf("%d\n",ans); ???return 0;}[Jsoi2015]染色问题
原文地址：https://www.cnblogs.com/asuldb/p/10775580.html