uva 11806 - Cheerleaders(容斥原理+二進制)

uva 11806 - Cheerleaders(容斥原理+二進制)

題意：

n行m列網格放k個石子。有多少種方法？要求第一行，第一列，最後一行，最後一列必須有石子。

思路：

1.利用容斥原理的拓展

假設有三個集合 S 另有三個集合A B C，不屬於 A、B、C任何一個集合，但屬於全集S的元素， 奇數個減；偶數個加

此處是S為空集 A、B、C、D分別代表 行 列中的四種情況:

AUBUCUD = |A| + |B| + |C| + |D| - |AB| - |BC| - |AC| - |AD| - |BD| - |CD| + |ABC| + |ABD| + |ACD| + |BCD| - |ABCD|

如果在集合A或B中，相當於少了一行；如果在集合C或D中，相當於少了一列。

假定最後剩下row行、col列，方法數就是C(row*col,k)個

2.用二進制表示四種情況的搭配

3.計算組合數:C(n+1,k+1)=c(n,k+1)+(n,k)

#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define MOD 1000007
#define MAX 510
int c[MAX][MAX];
void C()//計算組合數
{
	memset(c,0,sizeof(c));
	c[0][0]=1;
	for(int i=0;i<=500;i++)
	{
		c[i][0]=c[i][i]=1;
		for(int j=1;j