题意
一个n*m的区域内,放k个啦啦队员,第一行,最后一行,第一列,最后一列一定要放,一共有多少种方法。
思路
设A1表示第一行放,A2表示最后一行放,A3表示第一列放,A4表示最后一列放,则要求|A1∧A2∧A3∧A4|
由容斥原理可知|∪Ai| = Σ|Ai| - Σ|Ai∧Aj| + …… (+-)|Ai∧Aj∧……∧Ak|.
再由德摩根定律得:∧Ai = Cu(∪Cu(Ai)),所以|∧Ai| = S - |∪Cu(Ai)|.(Cu表示集合的非)
然后令A表示不放第一行,B表示不放最后一行,C表示不放第一列,D表示不放最后一列。
ANS = ALL-A-B-C-D+AB+AC+AD+BC+BD-ABC-ABD-BCD+ABCD
代码
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)/2)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXNUM = 505;
int C[MAXNUM][MAXNUM];
void cal_C(int n, int mod){
mem(C, 0);
C[0][0] = 1;
for (int i = 1; i <= n; i ++){
C[i][0] = 1;
for (int j = 1; j <= i; j ++){
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
}
}
}
int main(){
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
cal_C(500, 1000007);
int t;
scanf("%d", &t);
for (int icase = 1; icase <= t; icase++){
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
int ans = 0;
for (int i = 0; i < 16; i ++){
int bit = 0;
int r = n, c = m;
if (i & 1) r --, bit ++;
if (i & 2) r --, bit ++;
if (i & 4) c --, bit ++;
if (i & 8) c --, bit ++;
if (bit & 1){
ans = (ans - C[r*c][k] + 1000007) % 1000007;
}
else{
ans = (ans + C[r*c][k]) % 1000007;
}
}
printf("Case %d: %d
", icase, ans);
}
return 0;
}