[BZOJ4487][JSOI2015]染色问题(容斥)

一开始写了7个DP方程，然后意识到这种DP应该都会有一个通式。

三个条件：有色行数为n，有色列数为m，颜色数p，三维容斥原理仍然成立。

于是就是求：$\sum_{i=0}^{n}\sum_{j=0}^{m}\sum_{k=0}^{p}(-1)^{n+m+p-i-j-k}\times C_n^i\times C_m^j\times C_p^k\times (k+1)^{ij}$

复杂度$O(n^3)$

可以根据二项式定理优化：

https://blog.csdn.net/werkeytom_ftd/article/details/52527740

复杂度$O(n^2\log)$

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=,mod=1e9+;

 int n,m,p,ans,fac[N],inv[N];

 int ksm(int a,int b){

     int res=;

     for (; b; a=1ll*a*a%mod,b>>=)

         if (b & ) res=1ll*res*a%mod;

     return res;

 }

 int C(int n,int m){ return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod; }

 int main(){

     freopen("bzoj4487.in","r",stdin);

     freopen("bzoj4487.out","w",stdout);

     scanf("%d%d%d",&n,&m,&p);

     fac[]=; rep(i,,) fac[i]=1ll*fac[i-]*i%mod;

     inv[]=ksm(fac[],mod-);

     for (int i=; ~i; i--) inv[i]=1ll*inv[i+]*(i+)%mod;

     rep(i,,n) rep(k,,p){

         int t=1ll*C(n,i)*C(p,k)%mod*ksm((-ksm(k+,i)+mod)%mod,m)%mod;

         if ((n+m+p-i-k)&) ans=(ans-t+mod)%mod; else ans=(ans+t)%mod;

     }

     printf("%d\n",ans);

     return ;

 }