UVa 11806 拉拉队（容斥原理）

https://vjudge.net/problem/UVA-11806

题意：

在一个m行n列的矩形网格里放k个相同的石子，有多少种方法？每个格子最多放一个石子，所有石子都要用完，并且第一行、最后一行、第一列、最后一列都得有石子。

思路：

如果考虑各种情况的话很复杂，设满足第一行没有石子的方案集为A，最后一行没有石子的方案集为B，第一列没有石子的方案集为C，最后一列没有石子的方案集为D，全集为S。

一个容斥原理的公式就可以解答出来，用二进制来枚举方案集的组合。

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <cmath>

 using namespace std;

 const int mod = ;

 const int maxn = +;

 int c[maxn][maxn];

 void init()

 {

     for (int i = ; i <= maxn; i++)

     {

         c[i][] = c[i][i] = ;

         for (int j = ; j < i; j++)   c[i][j] = (c[i - ][j] + c[i - ][j - ]) % mod;

     }

 }

 int main()

 {

     //freopen("D:\\input.txt", "r", stdin);

     int T;

     int kase = ;

     int n, m, k;

     scanf("%d", &T);

     init();

     while (T--)

     {

         scanf("%d%d%d", &n, &m, &k);

         int sum = ;

         for (int S = ; S<; S++)

         {

             //S=0时就相当于计算c[n*m][k],不考虑条件时的所有方法数

             int b = , row = n, col = m;

             if (S & )  { row--; b++; }

             if (S & )  { row--; b++; }

             if (S & )  { col--; b++; }

             if (S & ) { col--; b++; }

             if (b & )   sum = (sum + mod - c[row*col][k]) % mod;

             else sum = (sum + c[row*col][k]) % mod;

         }

         printf("Case %d: %d\n", ++kase, sum);

     }

     return ;

 }