TIOJ 1291 N箱M球

poao899    148K    150MS    G++    0.48K     2009-10-10 23:08:04                                      .

唔我排組渣耶= =+


好數學的DP(點頭

第一次見到不是O(1)輸出的DP(抖

是說知道是O(n)輸出後遞迴式就沒那麼難想了....吧XD


被雷到才寫得出來(倒


//*************************************************

#include<stdio.h>
#define M 1000000
int dp[201][201];
int n,m,total;
main(){
    dp[0][0]=1;
    for(int i=1;i<201;i++)
        for(int j=1;j<201;j++)
            dp[i][j]=1;
    for(int i=1;i<201;i++)
        for(int j=1;j<201;j++){
            if(i<=j)dp[i][j]=(dp[i-1][j-1]+dp[i][j-1]*i)%M;
            else dp[i][j]=0;
        }
    while(scanf("%d%d",&n,&m),n+m){
        total=0;
        for(int i=1;i<=n;i++)
            total=(total+dp[i][m])%M;
        printf("%d\n",total);
    }
}