题目的大意就是在一个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