uva 11806 Cheerleaders （容斥）-白红宇

uva 11806 Cheerleaders （容斥）

阅读量：6274 次

发布时间：2019-06-22

本文共 1378 字，大约阅读时间需要 4 分钟。

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

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           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 }