[bzoj4487][Jsoi2015]染色_容斥原理
染色 bzoj-4487 Jsoi-2015
题目大意：给你一个n*m的方格图，在格子上染色。有c中颜色可以选择，也可以选择不染。求满足条件的方案数，使得：每一行每一列都至少有一个格子被染色，且所有的颜色必须都出现过。
注释：$1\le n,m,k\le 400$。
想法：显然直接求每个求，我们不难想到容斥原理。
我们用容斥来求出i行不染，j列不染，还剩(n-i)*(m-j)个格子这样我么根据那个容斥原理，先不考虑最后的条件；最后再将最后的信息加上。
可以得到式子。
$\sum\limits_{i=0}^n\sum\limits_{j=0}^m\sum\limits_{c=0}^k(-1)^{i+j+k}C_n^iC_m^jC_c^kk^{(n-i)(m-j)}$
由于n,m,k的范围问题，我们直接暴力组合数+快速幂即可。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll c[410][410],before[160010];
int main()
{
int n,m,p;
ll ans=0;
scanf("%d%d%d",&n,&m,&p);
before[0]=c[0][0]=1;
for(int i=1;i<=n||i<=m||i<=p;i++)
{
c[i][0]=1;
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
for(int i=0;i<=p;i++)
{
for(int j=1;j<=n*m;j++)before[j]=before[j-1]*(p-i+1)%mod;
for(int j=0;j<=n;j++)
for(int k=0;k<=m;k++)
ans=(ans+c[p][i]*c[n][j]%mod*c[m][k]%mod*before[(n-j)*(m-k)]%mod*((i^j^k)&1?-1:1)+mod)%mod;
}
printf("%lld\n",ans);
return 0;
}
小结：容斥原理好方便啊???！！
