uva 11806 Cheerleaders （容斥）

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2906

　　容斥原理，从反面去想。统计边界上都没有石子的情况。这时候就要用到容斥原理了。

代码如下：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 const LL MOD = 1000007;
10 const int N = 25;
11 const int M = N * N;
12 LL C[M][M];
13 
14 void PRE() {
15     C[0][0] = 1;
16     for (int i = 1; i < M; i++) {
17         C[i][0] = 1;
18         for (int j = 1; j <= i; j++) {
19             C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
20         }
21     }
22 }
23 
24 int main() {
25     int n, m, k, T, cas = 1;
26     PRE();
27     cin >> T;
28     for (int cas = 1; cas <= T; cas++) {
29         cin >> n >> m >> k;
30         LL ans = 0;
31         for (int i = 0; i < 16; i++) {
32             int r = n, c = m, odd = false;
33             if (i & 1) r--, odd = !odd;
34             if (i & 2) r--, odd = !odd;
35             if (i & 4) c--, odd = !odd;
36             if (i & 8) c--, odd = !odd;
37             if (r < 0 || c < 0) ;
38             else if (odd) ans -= C[r * c][k];
39             else ans += C[r * c][k];
40             while (ans < 0) ans += MOD;
41             while (ans >= MOD) ans -= MOD;
42         }
43         printf("Case %d: ", cas);
44         cout << ans << endl;
45     }
46     return 0;
47 }

View Code

——written by Lyon