4487: [Jsoi2015]染色问题
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 211 Solved: 127
[Submit][Status][Discuss]
Description
棋盘是一个n×m的矩形，分成n行m列共n*m个小方格。现在萌萌和南南有C种不同颜色的颜料，他们希望把棋盘用这些颜料染色，并满足以下规定：
1. 棋盘的每一个小方格既可以染色（染成C种颜色中的一种） ，也可以不染色。
2. 棋盘的每一行至少有一个小方格被染色。
3. 棋盘的每一列至少有一个小方格被染色。
4. 种颜色都在棋盘上出现至少一次。
以下是一些将3×3棋盘染成C = 3种颜色（红、黄、蓝）的例子：
请你求出满足要求的不同的染色方案总数。只要存在一个位置的颜色不同，
即认为两个染色方案是不同的
Input
输入只有一行 3 个整数n,m,c。1 < = n,m,c < = 400
Output
输出一个整数，为不同染色方案总数。因为总数可能很大，只需输出总数
mod 1,000,000,007的值。
Sample Input
2 2 3
Sample Output
60
HINT
Source
由一维容斥推到三维容斥。。
很诡异,并不是很懂,感性理解
枚举ijk,表示占据i行j列k个颜色或不涂色任意选
容斥就好了。
这样推出式子是O(N^3),根据二项式定理可以优化至O(N^2*log2(M))
看blog
http://blog.csdn.net/nirobc/article/details/51064832
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#define N 403#define p 1000000007#define LL long long using namespace std;int n,m,c;LL C[N][N];LL quickpow(int num,int x){ ???LL ans=1,base=num; ???while (x) { ???????if (x&1) ans=ans*base%p; ???????x>>=1; ???????base=base*base%p; ???} ???return ans;}int main(){ ???scanf("%d%d%d",&n,&m,&c); ???for (int i=0;i<=400;i++) C[i][0]=1; ???for (int i=1;i<=400;i++) ????for (int j=1;j<=i;j++) ?????C[i][j]=(C[i-1][j]+C[i-1][j-1])%p; ???LL ans=0; ???for (int k=0;k<=c;k++) { ????????LL x=1; ????????for (int i=n;i>=0;i--){ ???????????LL tot=1; ???????????for (int j=m;j>=0;j--) { ???????????????int t=i+j+k; ???????????????LL now=C[n][i]*C[m][j]%p*C[c][k]%p*tot%p; ???????????????if (t&1) ans-=now; ???????????????else ans+=now; ???????????????tot=tot*x%p; ????????????} ????????????x=x*(c-k+1)%p; ??????????????ans%=p; ????????} ???} ???printf("%lld\n",(ans%p+p)%p);}4487[Jsoi2015]染色问题 容斥+组合
原文地址：http://www.cnblogs.com/wsy01/p/8031109.html