HDU-1799(組合遞推公式)，hdu-1799遞推公式

HDU-1799(組合遞推公式)，hdu-1799遞推公式

                                               HDOJ-1799 - Fighting_Dream 

 

M - 暴力求解、打表 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u  

Description

  我們知道，在編程中，我們時常需要考慮到時間復雜度，特別是對於循環的部分。例如， 
如果代碼中出現 
for(i=1;i<=n;i++) OP ; 
那麼做了n次OP運算，如果代碼中出現 
fori=1;i<=n; i++) 
  for(j=i+1;j<=n; j++) OP; 
那麼做了n*(n-1)/2 次OP 操作。 
現在給你已知有m層for循環操作，且每次for中變量的起始值是上一個變量的起始值＋1（第一個變量的起始值是1），終止值都是一個輸入的n，問最後OP有總共多少計算量。   

Input

  有T組case，T<=10000。每個case有兩個整數m和n，0<m<=2000，0<n<=2000.  

Output

  對於每個case，輸出一個值，表示總的計算量，也許這個數字很大，那麼你只需要輸出除1007留下的余數即可。  

Sample Input

2 1 3 2 3  

Sample Output

3 3  

題目分析：

注意觀察到，可以發現循環的值是；C(n,m)=n!/((n-m)!*m!)，因為n值過大，不可以直接用公式

組合數學的遞推公式：C(n,m)=C(n,m-1)+C(n-1,m-1)，只要知道了這個問題就可以解決了

  注意：

全排列問題,C(n,m)=n!/(m!*(n-m)!)

 但是考慮到n的值過大,不能用這個方法
 可以用組合公式C(n,m)=C(n-1,m)+C(n-1,m-1)
 C(n,1)=n; C(n,n)=1; C(n,0)=1;

AC代碼：

# include<stdio.h>
int c[2001][2001];
void juge()
{
    for(int i= 1; i<= 2000; i++)
    {
        c[0][0] = 1;
        c[i][0] = 1;
        for(int j=1; j<= 2000; j++)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % 1007;  //組合公式
    }
}
int main()
{
    int T, n, m;
    juge();
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &m, &n);
        printf("%d\n", c[n][m]);
    }
}