TIOJ 1103 F.假日的奇想曲

 nolonger    108K    781MS    G++     0.24K     2009-10-21 19:59:58                            .

唔好陰險這題


"如果答案超過10000，只要輸出最後四位數就好。"

"最後四位"orz

謝謝書泓(?

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

#include
int dp[20010];
int way[10001];
int n;
main(){
    dp[0]=1;
    for(int i=1;i<=10000;way[i]=dp[2*i],i++)
        for(int j=1;j<=i*2;j++)
            dp[j]=(dp[j]+dp[j-1])%10000;
    while(scanf("%d",&n),n)
        printf(n>7?"%04d\n":"%d\n",way[n]);
}