UVa 11806 组合数+容斥原理

 1 #include <cstdio>
 2 #include <cstring>
 3 const int maxn = 405;
 4 const int mod = 1000007;
 5 int c[maxn][maxn];
 6 void init()
 7 {
 8     memset(c,0,sizeof(c));
 9     c[0][0] = 1;
10     for(int i = 1;i<maxn;++i)
11     {
12         c[i][0] = c[i][i] = 1;
13         for(int j = 1;j<i;++j)
14             c[i][j] = (c[i-1][j]+c[i-1][j-1])%mod;
15     }
16 }
17 int main()
18 {
19     init();
20     int n,m,k;
21     int T;scanf("%d",&T);
22     for(int kase = 1;kase <= T;++kase)
23     {
24         scanf("%d%d%d",&n,&m,&k);
25         if(k>n*m){printf("Case %d: 0\n",kase);continue;}
26         int sum = 0;
27         for(int s = 0;s<16;++s)
28         {
29             int r = n,l = m,b = 0;
30             if(s&1)r--,b++;
31             if(s&2)r--,b++;
32             if(s&4)l--,b++;
33             if(s&8)l--,b++;
34             if(b&1)sum = (sum+mod-c[r*l][k])%mod;
35             else sum = (sum+c[r*l][k])%mod;
36         }
37         printf("Case %d: %d\n",kase,sum);
38     }
39 
40     return 0;
41 }