UVA11806Cheerleaders（容斥）

转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud

题目意思：在m行n列的矩形网格中放k个相同的石子，问有多少中方法？每个格子最多放一个石子，所有石子都要用完，并且第一行，最后一行，第一列，最后一列都必须有石子。

分析：容斥入门水题

设第一行不放石子为事件A，最后一行不放为B，第一列不放为C，最后一列不放为D

则要求的即为这四个事件的补集的交集。接下来的步骤可通过容斥比较容易的推出。

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 int dp[510][510];
 5 const int MOD=1000007;
 6 int main()
 7 {
 8     ios::sync_with_stdio(false);
 9     int n,m,k,t;
10     dp[0][0]=1;
11     for(int i=1;i<510;i++)
12     {
13         dp[i][0]=dp[i][i]=1;
14         for(int j=1;j<i;j++)
15         {
16             dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%MOD;
17         }
18     }
19     cin>>t;
20     int cas=1;
21     while(t--)
22     {
23         cin>>n>>m>>k;
24         int ans=0;
25         for(int i=0;i<16;i++)
26         {
27             int r=n,c=m,f=0;
28             if(i&1){r--,f++;}
29             if(i&2){r--,f++;}
30             if(i&4){c--,f++;}
31             if(i&8){c--,f++;}
32             if(f&1)ans=(ans-dp[r*c][k]+MOD)%MOD;
33             else ans=(ans+dp[r*c][k])%MOD;
34         }
35         cout<<"Case "<<cas++<<": "<<ans<<endl;
36     }
37 
38     return 0;
39 }

View Code