Monday, August 25, 2014

uva : 530 - Binomial Showdown

#include<stdio.h>
int main()
{
    long n,m;
    while(scanf("%ld %ld",&n,&m)==2)
    {
        if(n==0&&m==0)
           break;
        else if(n==0&&m==1)
        {
            printf("1\n");
        }
        else{
        long  num1[1000],lnum1=1,i,j,k,l,r=0,div[1000],ldiv=0;
        long sum=1;
        num1[0]=1;
        l=n-m;
        if(l<m)
        {
            for(i=m+1;i<=n;i++)
            {
                for(j=0;j<lnum1;j++)
                {
                    k=(num1[j]*i+r)%10;
                    r=(num1[j]*i+r)/10;
                    num1[j]=k;
                }
                while(r!=0)
                {
                    num1[lnum1++]=r%10;
                    r=r/10;
                }
            }
            for(i=2;i<=l;i++)
            {
                sum=sum*i;
            }
        }
        else
        {
            for(i=l+1;i<=n;i++)
            {
                for(j=0;j<lnum1;j++)
                {
                    k=(num1[j]*i+r)%10;
                    r=(num1[j]*i+r)/10;
                    num1[j]=k;
                }
                while(r!=0)
                {
                    num1[lnum1++]=r%10;
                    r=r/10;
                }
            }
            for(i=2;i<=m;i++)
            {
                sum=sum*i;
            }
        }
        j=0;k=0;
        for(i=lnum1-1;i>=0;i--)
        {
            k=(num1[i]+r*10)/sum;
            r=(num1[i]+r*10)%sum;
            if(k>0)
            {
                j=1;
            }
            if(j==1)
            {
                div[ldiv++]=k;
            }
        }
        for(i=0;i<ldiv;i++)
        {
            printf("%ld",div[i]);
        }printf("\n");
    }
    }
    return 0;
}

No comments:

Post a Comment