1446.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1446 on 2005-03-19 at 11:47:27 */ 
#include <stdio.h>
#include <stdlib.h>

int combinat(int m, int n);

int main()
{
    int a, b;
    
    while(scanf("%d %d", &a, &b) == 2){
        if((a == 0) && (b == 0)){
            return 0;
        }else{
            printf("%d\n", combinat(a, b));
        }
    }    
            
    return 0;
}

int combinat(int m, int n)
{
    int i, j;
    int *mat = NULL, k, mats;
    
    if (n == 0 || m == n){
        return 1;
    }else if(n == 1 || n == m - 1){
        return m;
    }else{
        if(2 * n > m){
            n = m - n;
        }
        k = m - n;    
        mat = (int*)malloc(sizeof(int)*(n*(k+1)+1));
        for(j = 0; j < n; j++){
            mat[j] = 1;
            for(i = 1; i <= k; i++){
                if(j == 0){
                    mat[j+i*n] = i+1;
                }else{
                    mat[j+i*n] = mat[j+(i-1)*n] + mat[(j-1)+i*n];
                }
            }        
        }
        mats = mat[(n-1)+k*n];
        free(mat);
        return mats;
    }
}