首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。