uva 11806 - Cheerleaders

点击打开链接

题意：在一个n行m列的矩形里面放k个相同的石子，要求第一行，最后一行，第一列，最后一列都要有石子。问有几种方法？

思路：

1 如果题目没有要求“第一行，最后一行，第一列，最后一列都要有石子”，那么答案就是C[n*m][k]，我们用C[i][j]表示i个里面选择j个的组合数。

2 设满足“第一行没有石子“的集合为A，“第一列没有石子“的集合为B，“最后一行没有石子“的集合为C，“最后一列没有石子“的集合为D，那么答案就是C[n*m][k]-|A∪B∪C∪D|。

   |A∪B∪C∪D|就是容斥原理，有四个集合总的就有2^4-1种结果。

   比如|A∪B∪C| = |A| +|B| +|C| - |AuB| - |AuC| - |BuC| + |AnBnC|3 那么我们只要枚举15种情况即可

代码：

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int MOD = 1e6+7;
const int MAXN = 510;

int n , m , k;
int C[MAXN][MAXN];

void init(){
	memset(C , 0 , sizeof(C));
	C[0][0] = 1;
	for(int i = 0 ; i < MAXN ; i++){
		C[i][0] = C[i][i] = 1;
		for(int j = 1 ; j < i ; j++)
			C[i][j] = (C[i-1][j]+C[i-1][j-1])%MOD;
	}
}

int solve(){
	int ans = 0;
	// 枚举15种情况
	for(int s = 1 ; s < 16 ; s++){
        int cnt = 0;
		int r = n;
		int c = m;
		if(s&1){
			cnt++;
            r--;
		}
		if(s&2){
			cnt++;
			c--;
		}
		if(s&4){
			cnt++;
            r--;
		}
		if(s&8){
			cnt++;
			c--;
		}
		// 如果是奇数个是相加
		if(cnt&1){
			ans = (ans+C[r*c][k])%MOD;
		}
		else{
			ans = (ans-C[r*c][k]+MOD)%MOD;
		}
	}
	return (C[n*m][k]-ans+MOD)%MOD;
}

int main(){
    init();
	int cas , Case = 1;
	scanf("%d" , &cas);
	while(cas--){
		scanf("%d%d%d" , &n , &m , &k);
		printf("Case %d: " , Case++);
		cout<<solve()<<endl;
	}
	return 0;
}