题意

一个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\n", icase, ans);	}	return 0;}