题目描述
华科校园的规划相当整齐,横平竖直,只要知道方向,你就不会迷路。具体是这样的,华科的校园是n*m的格子形状(如下所示),格子是建筑物,不能通过,只能走格子线,每走动一格花费时间1s。
现在有一个同学想用最短的时间从右上角走到左下角,请问他有多少种方法?上图表示了在4 * 5的格子上的可能的两种方法。
输入
多组数据,每组数据如下:
N M,其中N和M都在32位的整数范围内(0<=N<2^32-1, 0<=M<2^32-1)。
输入以文件尾(EOF)结束
输出
每组数据对应一个输出Z,表示其方案数(数据保证方案数也在32位的整数范围内)
样例输入
5 4 1 1
样例输出
126 2
这个题真的很强大,题目说保证在32位的数据,则我们肯定可以说,n和m中,一定有一个数很小,这样就可以求了,那么如果直接用求和公式,肯定会超64位,那怎么办,这里给出两个程序,一个有精度误差,一个则是正确的
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int main() { int n,m; while (scanf("%d%d",&n,&m)!=EOF) { int N=min(n,m); int M=max(n,m); double mm=0.0,MM=0.0; for (int i=1;i<=N;i++) mm+=log10(double(i)); for (int i=N+M;i>=M+1;i--) MM+=log10(double(i)); int sum=pow(10.0,MM-mm); printf("%d\n",sum); } return 0; }
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int main() { long long n,m; while (scanf("%lld%lld",&n,&m)!=EOF) { long long N=min(n,m); long long M=n+m; long long ans=1; for (long long i=1;i<=N;i++) ans=(ans*(M-i+1))/i; printf("%lld\n",ans); } return 0; }
hust 1445 无名题目C,布布扣,bubuko.com
原文:http://www.cnblogs.com/chensunrise/p/3710238.html