大致题意： 有一个\(n*m\)的矩形，先让你用\(C\)种颜色给它染色。每个格子可染色可不染色，但要求每行每列至少有一个小方格被染色，且每种颜色至少出现一次。求方案数。
高维容斥
显然题目中给你\(3\)个条件，而我们要一起容斥，所以就是高维容斥。。。
通过高维容斥，我们可以得到这样一个式子：
\[\sum_{i=0}^n(-1)^{n-i}C_n^i\sum_{j=0}^m(-1)^{m-j}C_m^j\sum_{k=0}^c(-1)^{c-k}C_c^k(k+1)^{ij}\]
然后我们把三个\(\sum\)提前，就可以得到这样一个式子：
\[\sum_{i=0}^n\sum_{j=0}^m\sum_{k=0}^c(-1)^{n+m+c-i-j-k}C_n^iC_m^jC_c^k(k+1)^{ij}\]
可以发现，这个式子可以\(O(nmc)\)推，做这题\(n,m,c\le400\)的数据已经足够了。
二项式定理
虽说原先的式子已经能水过了，但这题其实可以优化至\(O(nclog_2m)\)。
首先我们要知道二项式定理是这样一个式子：
\[(x+y)^n=\sum_{i=0}^nC_n^ix^iy^{n-i}\]
然后我们就要考虑将上面的式子转化，使其能够用二项式定理化简：
\[\sum_{i=0}^n\sum_{k=0}^c((-1)^{n+m+c-i-k}C_n^iC_c^k\sum_{j=0}^mC_m^j(-1)^{-j}((k+1)^i)^j)\]
接下来我们单独考虑其中\(\sum_{j=0}^mC_m^j(-1)^{-j}((k+1)^i)^j\)。
观察可得，这个式子中枚举上界为\(m\)，有一个组合数\(C_m^j\)，且\(((k+1)^i)^j\)一项为\(j\)次项，因此我们要把另一项变成\((m-j)\)次项。
也就是我们要乘上一个\((-1)^m\)。
于是就能得到这样一个式子：
\[(-1)^{-m}\sum_{j=0}^mC_m^j(-1)^{m-j}((k+1)^i)^j\]
\[(-1)^{-m}(-1+(k+1)^i)^m\]
考虑当\(m\)为奇数时，\((-1)^{-m}=-1\)，可得：
\[(1-(k+1)^i)^m\]
考虑当\(m\)为偶数时，\((-1)^{-m}=-1\)，考虑到一个数与其相反数的偶次幂相等，可得：
\[(1-(k+1)^i)^m\]
因此，原始可以简单地归纳为一个式子。
再把这个式子代回整个式子中，就得到：
\[\sum_{i=0}^n\sum_{k=0}^c((-1)^{n+m+c-i-k}C_n^iC_c^k(1-(k+1)^i)^m\]
而这个式子就可以\(O(nclog_2m)\)求解了。
代码
#include#define Tp template #define Ts template #define Reg register#define RI Reg int#define Con const#define CI Con int&#define I inline#define W while#define N 400#define X 1000000007#define Qinv(x) Qpow(x,X-2)#define Inc(x,y) ((x+=(y))>=X&&(x-=X))#define Dec(x,y) ((x-=(y))<0&&(x+=X))#define C(x,y) (1LL*Fac[x]*Inv[y]%X*Inv[(x)-(y)]%X)#define swap(x,y) (x^=y^=x^=y)using namespace std;int n,m,c,Fac[N+5],Inv[N+5];I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}//快速幂I int XSub(RI x,CI y) {return Dec(x,y),x;}//模意义下做减法int main(){ RI i,k,t,ans=0;for(scanf("%d%d%d",&n,&m,&c),t=max(n,c),Fac[0]=i=1;i<=t;++i) Fac[i]=1LL*Fac[i-1]*i%X;//初始化阶乘 for(Inv[t]=Qinv(Fac[t]),i=t-1;~i;--i) Inv[i]=1LL*Inv[i+1]*(i+1)%X;//初始化阶乘逆元 for(i=0;i<=n;++i) for(k=0;k<=c;++k)//枚举i和k，求解答案 { if((n+m+c-i-k)&1) Dec(ans,1LL*C(n,i)*C(c,k)%X*Qpow(XSub(1,Qpow(k+1,i)),m)%X); else Inc(ans,1LL*C(n,i)*C(c,k)%X*Qpow(XSub(1,Qpow(k+1,i)),m)%X); } return printf("%d",ans),0;//输出答案}