学步园

这段时间老是遇到这种题目呀，就是所谓容斥原理的题目，比如第一章的1.24（猛一下还没有想起来具体的题意……一会得去看看）。

这道题目，我自己做的是分情况讨论，还用了什么Lucas，也都忘了，到最后也没有写对，一看题解，就又崩溃了。

题目的描述是：在一个N*M的矩阵中放拉拉队员，但是这里的拉拉队员可得想象成一样的东西，比如石子什么的。题解上想象成了石子。然后问你，四周必须至少有一个石子。问你有多少种可能。

想象有这样4个集合：第一个A代表第一行没有石子，B代表最后一行没有石子，C代表第一列没有石子，D代表最后一列没有石子。那么题目的问题就转换成了：求在全集的条件下，既不在A中也不在B，C，D的种类。

然后就用到了容斥定理，就是S-A-B+A交B 这就是一个简单的容斥定理。需要注意的是，奇数个的时候用减法，偶数个的时候用加法。这个对于一般的枚举都管用。

贴出代码，时常复习吧：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>

using namespace std;

const int MAXN = 511;

const int MOD = 1000000 + 7;

int N, M, K;

long long C[MAXN][MAXN];

void init()
{
	memset(C, 0, sizeof(C));
	C[0][0] = 1; //这个是一定要注意的,因为你初始化的时候给初始化成0了,而实际的值是1,
	for (int i = 1; i < MAXN; i++)  //虽然这里将C[0][0]赋值为1了,但是还是要提醒自己. 
	{
		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;
		}
	}
	/*
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < i; j++)
		{
			printf("C[%d][%d] = %d\n", i, j, C[i][j]);
		}
	}
	*/
}

int main()
{
	int T;
	init();
	scanf("%d", &T);
	for (int Case = 1; Case <= T; Case++)
	{
		scanf("%d%d%d", &N, &M, &K);
		int sum = 0;
		for (int i = 0; i < (1 << 4); i++)
		{
			int r = N;
			int c = M;
			int b = 0;
			if (i & 1)
			{
				r--;
				b++;
			}
			if (i & 2)
			{
				r--;
				b++;
			}
			if (i & 4)
			{
				c--;
				b++;
			}
			if (i & 8)
			{
				c--;
				b++;
			}
			if (b & 1)
			{
				sum = (sum - C[r * c][K] + MOD) % MOD;
			}
			else
			{
				sum = (sum + C[r * c][K]) % MOD;
			}
		}
		printf("Case %d: %d\n", Case, sum % MOD);
	}
//	system("pause");
	return 0;
}