Description

    笨笨当了很久的道路调度员，笨笨也开始想体验生活，从生活中发现数学问题，锻炼自己思维。最近《变形金刚3》，《哈利波特7》同步放映，明显是决战雌雄，已知王府井中一共有n人买了《变形金刚3》的票，m人买了《哈利波特7》的票，并且n>=m，并且电影院中现在只有两种票，每次只有一个人买，(共有n+m次)，这n+m次组成一个排列，为了保证每一个人买票时，《变形金刚3》票房都不少于《哈利波特7》，(n个买《变形金刚3》的人之间没区别，m个买《哈利波特7》的人也没区别),笨笨想着到这样的购票方案有多少种。笨笨想了好久都没想出来，所以笨笨找到了你。

 

Input

一行两个数n,m (  0<=m<=n<=5000)

Output

    输出方案种数

Sample Input

1 1

Sample Output

1

Data Constraint

Hint

0<=m<=n<=5000

解析

刚看到题里面开始暴力找规律，发现  (i,j为答案，也就是分别模拟 n，m)

扫一眼数据,才5000？？？（咳咳，当我没说），担心 f 存不下，于是想了各种方法搞定，测一下数据（只能过35！！！Σ(⊙▽⊙"a ）

好吧，顿时萎了，想着打完二三题暴力在来打高精度，结果打出来了，调到一半就结束了。

这个事情告诉我们什么？高精，高精，随时能让人萎了。

--------------------------------------好了，接下来才是正解，以上是赛时内心吐槽-------------------------------

假设将买《变形金刚3》票的人记为s 。买《哈利波特7》的人记为x 

,则n个买《变形金刚3》的与m个买《哈利波特7》的人的队伍就可以用一个具有n个s和m个x的字符串，显然这样的字符串共有C(n+m,n）个，

其中不满足问题要求的串一定存在一个最靠左的位置p，使得从第一个字符到第p个字符为止的子串中x的个数比s的个数大1.

如sxsxx就是一个不满足条件的串，其中p=5。

我们将从头到p为止的子串中的字符s换成x则得到一个具有n+1个s，m-1个x的串，可以证明这种转换是一一对应的，即任意一个n+1个s，m-1个x的串都可以按照逆规则转换成一个不满足题目条件的串，

转换规则为在任意一个n+1个s，m-1个x中找到最靠左的p，使得从头到p的子串中s的个数比x个数大1，将到p为止的子串中的s与x互换则得到n个s和m个x的串，且此串一定不能满足条件，而具有n+1个s，m-1个x的串只有C(n+m,n+1）。

那么ans=C(n+m,n)-C(n+m,n+1)=(n+1-m)*(m+n)!/(m!*(n+1)!)种方案可满足条件。

由于问题的规模很大，结果远远超出longint，要用高精度算法，（呵呵，别调萎了）

虽然结果表达式中有分母，但实际结果一定是整数，所以不需要除法运算，

具体运算时只要求出(n+1-m)*(m+n)!/(m!*(n+1)!的质因子分解式，然后做高精度即可，而任意一个质因子r在n！中出现次数为[n/r]+[n/(r^2)]+[n/(r^3)]+...[n/(r^k)]，[]为取整。

（摘自jzoj题解）

 

CODE（jio个biu四偶记几的）

constmo=1000000000;
varans:array[0..10000000]of int64;n,m,sum,k:int64;i,j:longint;
procedure jc(k:longint);
varsum:int64;i:longint;
beginfor i:=1 to ans[0] do beginans[i]:=ans[i]*k+sum;sum:=ans[i] div mo;ans[i]:=ans[i] mod mo;end;while (sum<>0) do begininc(ans[0]);ans[ans[0]]:=sum;sum:=sum div mo;end;
end;
procedure chu(k:longint);
vari:longint;
beginfor i:=ans[0] downto 1 do beginans[i-1]:=ans[i-1]+ans[i] mod k*mo;ans[i]:=ans[i] div k;end;while (ans[ans[0]]=0) do dec(ans[0]);
end;
beginreadln(n,m);ans[0]:=1;ans[1]:=1;for i:=n+2 to n+m do jc(i);jc(n+1-m);for i:=1 to m do chu(i);write(ans[ans[0]]);for i:=ans[0]-1 downto 1 do begink:=ans[i];sum:=0;while (k>0) do begininc(sum);k:=k div 10;end;for j:=1 to 9-sum do write('0');write(ans[i]);end;
end.