1942 无重全排列.cpp

各种算法

#include"stdio.h"
__int64 c(__int64 n,__int64 k)
{	if(k == 0) return 1;
	return c(n-1,k-1)*n/k;
}
int main()
{	__int64 m,n;__int64 ans;
	while(scanf("%I64d%I64d",&m,&n)!=0 && m+n != 0)
	{	ans = c(m+n,m>n?n:m);
		printf("%I64d\n",ans);
	}
	return 1;
}
/*
简单格路问题  |(0,0)→(m,n)|=(       )
从 (0,0)点出发沿x轴或y轴的正方向每步
走一个单位，最终走到(m,n)点，有多少
条路径？
无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。
则(0,0)→(m,n)的每一条路径可表示为m 个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。
设所求方案数为p(m+n；m，n)
则P(m+n；m，n)·m!·n!=(m+n)!
故P(m+n;m,n)= (m+n)! /(m!n!)=C(m+n,n)=C(m+n,m)
设c≥a,d≥b,则由(a,b)到(c,d)的简单格路数为|(a,b)(c,d)|=p(c-a+d-b,c-a);
*/