摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:數學 組合(巴斯卡三角形)
想法:1.先將C(3000,n-1)前面(含)的組合算好 2.請參考下面
說明:C(N,M) 代表N取M的組合 這樣OK嗎? 數據可能會有錯誤 不過大致上的想法是這樣 數據錯誤請幫忙修改 我頭好痛...測試了好久...
ex:
3
12 34 56

      56
       .
       .
      35 (這邊直接加就可以了)
   34
   33 C(2966,1)
    .
    .
    .
   13 C(2986,1)
12
11 C(2988,2)
10 C(2987,2)
9  C(2986,2)
.
.
.
1  C(2998,2)
0  C(2999,2) 2999 是1~2999 的個數去做組合 2是後面有2個位子可以選

 

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

#include<stdio.h>
#include<stdlib.h>
#define N 10000000
int math[3001][3001]={0};
main()
{
 int a,b,c;
 math[1][1]=1;
 for(a=0;a<3001;a++)  math[a][0]=1;
 for(a=2;a<3001;a++)
  {
   for(b=1;b<a;b++)
     math[a][b]=(math[a-1][b-1]+math[a-1][b])%N;
    math[a][b]=1;
  }
 int n;
 while(scanf("%d",&n)!=EOF)
  {
    int num[3000],ans=0,before=0;
    for(a=0;a<n;a++) scanf("%d",&num[a]);
    for(a=0;a<n-1;a++) before=(before+math[3000][a+1])%N;
    for(a=0;a<n-1;a++)
       {
         if(a-1>=0)
         for(b=num[a-1]+1;b<num[a];b++)
           {
            ans=(ans+math[3000-b-1][n-a-1])%N;
           }
         else
         for(b=1;b<=num[a];b++)
           {
            ans=(ans+math[3000-b][n-a-1])%N;
           }
       }
    if(n>1)
     ans=(ans+num[n-1]-num[n-2])%N;
    else
     ans=num[0]+1;
    printf("%07d\n",(ans+before)%N);
  }
 return 0;
}