Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

0ms代码

Posted by meJustPlay at 2012-05-20 12:32:51 on Problem 2249
/**
 * POJ: 2249 Binomial Showdown
 *
 * 大数: 组合数 C(n, m) = C(n, n-m) = C(n-1, m-1) + C(n-1, m) 
 *              C(n, m) = n! / [m! * (n - m)!]
 *              两边同取ln对数
 *
 * 注意: 本题不能开数组: e.g. C(INT_MAX, 1)
 */

/** *****/
#include <stdio.h>
#include <math.h>

/** *****/
#define ONLINE_JUDGE	1

/** *****/
double resolve(int n, int m)
{
	int low = m;
	int upp = n - m;
	
	double a = 0.0;
        double b = 0.0;

	if (upp > low) {
		upp ^= low;
		low ^= upp;
		upp ^= low;
	}

	for (int i = low + 1; i <= n; ++i) {
		a += log((double)i);
	}

	for (int i = 1; i <= upp; ++i) {
		b += log((double)i);
	}

	return exp(a - b);	// 此处不能类型转换
}

/** *****/
int main(int argc, char **argv)
{
	#ifndef ONLINE_JUDGE
	freopen("input/2249", "r", stdin);
	#endif

	int m, n;

	while (2 == scanf("%d%d", &n, &m) && n) {
		if (m > (n >> 1)) {
			m = n - m;
		}

		printf("%.0f\n", resolve(n, m));
		// "%ld",  取整数
		// "%.0f", 四舍五入
	}

	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator