UVA 11806 Cheerleaders

今天推了好久的一题，就是在矩形中放点，边界上必须有点。用数学语言就是：在一定数内取排列，其中某几段内必须有数被取。比！赛完以后才发现白书二代里面有原题，思路就是U－!A－!B－……+!A!B+!B!C+…… 就是数学中的容斥原理。

 1 #include <cstdio>
 2 const int Mod = 1e6+7;
 3 const int K = 500;
 4 int C[K+10][K+10];
 5 int main()
 6 {
 7     for(int i = 0; i <= K; i++)
 8     {
 9         C[i][0] = C[i][i] = 1;
10         for(int j = 1; j < i; j++)
11             C[i][j] = (C[i-1][j]+C[i-1][j-1])%Mod;
12     }
13     int T,m,n,k,r,c,b,s,ans,cas=1;
14     scanf("%d",&T);
15     while(T--)
16     {
17         scanf("%d%d%d",&n,&m,&k);
18         ans = 0;
19         for(s = 0; s < 16; s++)
20         {
21             b = 0; r=n; c=m;
22             if(s&1){r--;b++;}
23             if(s&2){r--;b++;}
24             if(s&4){c--;b++;}
25             if(s&8){c--;b++;}
26             if(b&1) ans = (ans-C[r*c][k])%Mod;
27             else ans = (ans+C[r*c][k])%Mod;
28         }
29         ans = (ans+Mod)%Mod;
30         printf("Case %d: %d\n",cas++,ans);
31     }
32     return 0;
33 }