POJ 2249-Binomial Showdown(排列组合计数)

Binomial Showdown

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 18457		Accepted: 5633

Description

In how many ways can you choose k elements out of n elements, not taking order into account?

Write a program to compute this number.

Input

The input will contain one or more test cases.

Each test case consists of one line containing two integers n (n>=1) and k (0<=k<=n).

Input is terminated by two zeroes for n and k.

Output

For each test case, print one line containing the required number. This number will always fit into an integer, i.e. it will be less than 2³¹.

Warning: Don't underestimate the problem. The result will fit into an integer - but if all intermediate results arising during the computation will also fit into an integer depends on your algorithm. The test cases will go to the limit.

Sample Input

Sample Output

题意：求C(n,m)；

思路：这个是当中一种办法。就是连乘r个整商：C(n,k)=C(n,k-1)*(n-k+1)/k。时间复杂度O(n);

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <algorithm>

#include <set>

#include <queue>

#include <stack>

#include <map>

using namespace std;

typedef long long LL;

LL work(LL n,LL m)

{

    if(m>n/2) m=n-m;

    LL a=1,b=1;

    for(int i=1;i<=m;i++){

        a*=n-i+1;

        b*=i;

        if(a%b==0){

            a/=b;

            b=1;

        }

    }

    return a/b;

}

int main()

{

    LL n,m;

    while(~scanf("%lld %lld",&n,&m)){

        if(!n&&!m) break;

        printf("%lld\n",work(n,m));

    }

    return 0;

}

巴特西

POJ 2249-Binomial Showdown(排列组合计数)

最新文章

热门文章