CSU暑期集訓day04_動態規劃_賽馬

NO IMAGE

題目:

    Disky and Sooma, two of the biggest mega minds of Bangladesh went to a far country. They ate, coded and wandered around, even in their holidays. They passed several months in this way. But everything has an end. A holy person, Munsiji came into their life. Munsiji took them to derby (horse racing). Munsiji enjoyed the race, but as usual Disky and Sooma did their as usual task instead of passing some romantic moments. They were thinking- in how many ways a race can finish! Who knows, maybe this is their romance!

    In a race there are n horses. You have to output the number of ways the race can finish. Note that, more than one horse may get the same position. For example, 2 horses can finish in 3 ways.

1. Both first

2. horse1 first and horse2 second

3. horse2 first and horse1 second

Input

Input starts with an integer T (≤ 1000), denoting the number of test cases. Each case starts with a line containing an integer n (1 ≤ n ≤ 1000).

Output

For each case, print the case number and the number of ways the race can finish. The result can be very large, print the result modulo 10056.

Sample Input

3

1

2

3

Sample Output

Case 1: 1

Case 2: 3

Case 3: 13

 

題目大意:

    給定馬的數量,求賽馬的可能結果的數量,每匹馬是不同的,它們可能一部分或全部並列到達終點。

解題思路:

    設num[p][q]表示p匹馬分為q批到達終點的可能結果的總數,顯然p大於等於q,根據第p匹馬到達終點的方式分類:若第p匹馬是和某一或某些馬同時到達終點,其餘p-1匹馬到達終點的結果數是num[p-1][q],而且第p匹馬可能是q批次中的任一批,所以這種類別下的結果數是q*num[p-1][q];若第p匹馬是單獨到達終點的,它可能是q批中的任一批,其餘p-1匹馬到達終點結果數是num[p-1][q-1],總共是q*num[p-1][q-1]。因此得到轉換方程num[p][q]=q*num[p-1][q] q*num[p-1][q-1]。

程式碼:

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

/*long long int fun(int n,int j){
    if(n==1||j==1)return 1;
    if(n==j)return j*(fun(n-1,j-1))%10056;
    return (j*((fun(n-1,j) fun(n-1,j-1))%10056))%10056;
}*/

int main(){
    int t;
    cin>>t;
    for(int i=1;i<=t;i ){
        int n;
        cin>>n;
        /*vector<vector<int> > num(1002);
        for(int p=0;p<1002;p ){
            num[p].resize(1002);
            for(int q=0;q<1002;q ){
                num[p][q]=0;
            }
        }*///用vector會超時 
        
        int num[1002][1002]={0};//直接用陣列部分編譯器會報錯,但是能AC 

        long long int ans[n 1]={0};
        num[1][1]=1;
        num[0][0]=1;
        for(int p=1;p<=n;p ){
            long long int sum=0;
            for(int q=1;q<=p;q ){
                num[p][q]=q*((num[p-1][q] num[p-1][q-1])%10056)%10056;
                sum=(sum num[p][q])%10056;
            }
            ans[p]=sum;
        }
        cout<<“Case “<<i<<“: “<<ans[n]<<endl; 
    }
    return 0;
}