容斥原理-shuoj—小明系列之高中時光

Description

小明是一個聰明的小孩，雖然國中沒有前三年學習成績都很差。但是憑借這中考前最後幾個月的沖刺還是考進了一所離家裡比較近的普通高中。剛進入高中小明對課堂上老師講授的問題依然沒有什麼興趣。但是小明的聰明頭腦依然不會停止轉動。平時隻要一閑下來就會去思考一些有趣的數學問題。今天小明學校開運動會，小明和他的同學們都坐在操場上觀看開幕儀式。愛思考的小明又閑不住了，正好小明身邊有k個石子，小明又在地闆上畫了一個m行n列的矩形網格，問題是有多少種方法可以将這k個石子放進網格裡？現在要你寫程式計算這個問題，看看你能不能借助計算機的力量算的比小明快。每個格子最多放一個石子，所有的石子必須用完，另外小明為了加大難度又加了一個條件：第一行、最後一行、第一列、最後一列都得有石子。

Input

輸入第一行為資料組數T（T<=50）,每組資料包含三個整數m,n,k（2<=m,n<=20,k<=500）。輸入資料至檔案結尾。

Output

對于每組資料輸出一行，方案總數除以1000007的餘數。

Sample Input

22 2 12 3 2

Sample Output

02

題解： 容斥原理（p(A+B) = p(A) + P(B) - P(AB)）  （百度連結，點選打開連結）。

組合數 （百度連結 點選打開連結）

本題主要運用了容斥原理和求組合數（組合數連結，點選打開連結）。

現在具體分析這道題。

四個邊上都有點的組合  =  總組合數  -  四個邊中至少有一個邊沒有點的組合數。

将問題轉化成 求：四個邊中至少有一個邊沒有點的組合數

用數組 dp[ i ][ j ]來儲存組合數C（i  ,  j）。

由容斥原理：

設A=  上邊沒點     B = 下邊沒點     C = 左邊沒點     D = 右邊沒點 四個邊中至少有一個邊沒有點  =  A + B +  C  + D -AB - AC - AD  - BC - BD  -CD + ABC + ABD + ACD + BCD - ABCD

分别求出上述獨立事件的組合數即為最終結果。

代碼如下：

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000007;
long long dp[405][405];

//将組合數打表
void com(){
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
    for(int i = 2;i<401;i++){
        for(int j = 0;j<=i;j++){
            if(j == 0||j == i)dp[i][j] = 1;
            else dp[i][j] = (dp[i-1][j-1]+dp[i-1][j])%mod;
        }
    }
}
int main(){
    com();
    int T;
    cin>>T;
    while(T--){
        int m,n,k;
        cin>>m>>n>>k;
         if(k<2||k>m*n)
        {
            cout<<0<<endl;
            continue;
        }
      long long sum;
      sum = (dp[n*m][k] - 2*dp[(n-1)*m][k] - 2*dp[n*(m-1)][k]+mod)%mod;
      while(sum<0)sum+=mod;
      sum = (sum + dp[(n-2)*m][k] + dp[(m-2)*n][k] + 4 * dp[(n-1)*(m-1)][k])%mod;
      while(sum<0)sum+=mod;
      sum = (sum - 2*dp[(n-2)*(m-1)][k] - 2*dp[(m-2)*(n-1)][k]+mod)%mod;
      while(sum<0)sum+=mod;
      sum = (sum + dp[(n-2)*(m-2)][k])%mod;
      while(sum<0)sum+=mod;
        cout<<sum<<endl;
    }
           

謝謝！