首页 > 代码库 > poj1942 Paths on a Grid 【排列组合】

poj1942 Paths on a Grid 【排列组合】

关于这个题想说一下,刚开始准备按照有一个含有n个数的非递减序列,每个数最大值为m,数字可以重复,有多少种这样的序列,像是一个蛮复杂的排列组合

其实这道题,从left bottom到right up只能向右或者向上,也就是m+n个格子里面取m个格子写右,n个格子写上,就成了个很2的排列组合问题

值得强调的是,这个题求组合数是用分数相乘来求的,怕double丢精度可以末尾+0.5然后转化为longlong来进行四舍五入

这个题int好像过不了

说个蛮逗比的。。。最近不是写了个交题的脚本么,本来是一水题,然后狂交了几次都TLE,看了看自己思路和题解是差不多的,把题解po过去,也是TLE,后来才发现,,没改题号。。。回到脚本文件改下题号就OK了。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
	#ifndef ONLINE_JUDGE
    	//freopen("/home/test/in.txt","r",stdin);
    	//freopen("/home/test/list.txt","w",stdout);
    #endif
    long long m,n;
    while(scanf("%lld%lld",&m,&n)!=EOF)
    {
    	if(!m&&!n)
    		break;
		long long sum=m+n;
		double res=1;
		for(long long i=min(m,n);i>=1;i--)
		{
			res*=sum--/(i*1.0);
		}
		/*long long res=com(sum,min(m,n));*/
		printf("%lld\n",(long long)(res+0.5));
    }
	return 0;
}