UVA 369: Combinations

Jasonlin posted @ 2011年3月30日 11:38 in UVA with tags 数学 组合数学 , 2004 阅读

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=5&problem=305&mosmsg=Submission+received+with+ID+8692218

题目大意:

GIVEN:

displaymath41

 

Compute the EXACT value of:

 

displaymath43

给你N和M求C。

解题思路:

      由于直接求出阶乘数据庞大,要用高精度算法。但是据题目说答案不超过32位,所以就用新的方法来做。把公式转化为

 

$$C=\frac{(M+1)*...*N}{(N-M)!}$$

然后把m+1到n都存入数组,用(n-m)到1去和数组的数一起除以它们的最大公约数。最后把数组里面的数相乘起来就是答案。

解题代码:

#include<iostream>
using namespace std;
typedef long long ll;
ll s[105];
ll gcd(ll a,ll b){
	return a%b==0?b:gcd(b,a%b);
}
int main(){
	ll n,m;
	while(cin>>n>>m&&m+n){
		for(int i=1;i<=n;i++)
			s[i]=i;
		ll t=n-m,sum=1;
		if(t!=0){
			while(t!=1){
				for(int i=m+1,j=t;i<=n&&j!=1;i++){
					ll g=gcd(s[i],j);
					s[i]/=g;
					j/=g;
				}
				t--;
			}
			for(int i=m+1;i<=n;i++)
				sum*=s[i];
		}
		cout<<n<<" things taken "<<m<<" at a time is "<<sum<<" exactly."<<endl;
	}
        return 0;
}

扩展知识:http://en.wikipedia.org/wiki/Combinatorics


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter