容斥原理u怎么读_三容斥原理所有公式

容斥原理u怎么读_三容斥原理所有公式题目的大意就是在一个m行n列的棋盘上放k颗棋子,要求是在第一行和最后一行,第一列和最后一列都有棋子,应该说分类的话,也可以做出来,但是比较繁琐,而且容易出错

容斥原理u怎么读_三容斥原理所有公式"

  题目的大意就是在一个m行n列的棋盘上放k颗棋子,要求是在第一行和最后一行,第一列和最后一列都有棋子,应该说分类的话,也可以做出来,但是比较繁琐,而且容易出错。

  解答可以用容斥定理,分别设A,B,C,D为第一行没有棋子,最后一行没有棋子, 第一列没有棋子,最后一列没有棋子,答案就是在棋盘上,但是不在ABCD上的。

  然后容斥定理计算即可,减去奇数情况的。

  

#include "stdio.h"
#include "string.h"
#include "math.h"
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

#define MAXM 1
#define MAXN 1
#define max(a,b) a > b ? a : b
#define min(a,b) a < b ? a : b
#define Mem(a,b) memset(a,b,sizeof(a))
int Mod = 1000007;
double pi = acos(-1.0);
double eps = 1e-6;

typedef struct{
	int f,t,w,next;
}Edge;
Edge edge[MAXM];
int head[MAXN];
int kNum;

void addEdge(int f, int t, int w)
{
	edge[kNum].f = f;
	edge[kNum].t = t;
	edge[kNum].w = w;
	edge[kNum].next = head[f];
	head[f] = kNum ++;
}

int C[505][505];

void func(){
	Mem(C, 0);
	for(int i = 0; i < 501; 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 m,n,k,T;

void solve(){
	int ans = 0;
	for(int i = 0; i < 16; i ++){
		int r = m, c = n, 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 ){
			ans = ( ans - C[r*c][k] + Mod) % Mod; 
		}
		else
			ans = ( ans + C[r*c][k] ) % Mod;
	}
	printf("%d\n",ans);
}


int main()
{
//	freopen("d:\\test.txt", "r", stdin);
	func();
	while(cin>>T){
		for(int i = 0; i < T; i ++){
			printf("Case %d: ", i + 1);
			cin>>m>>n>>k;
			solve();
		}
	}

	return 0;
}

今天的文章容斥原理u怎么读_三容斥原理所有公式分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/89079.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注