「CODEVS1515」跳

2015年1月9日2,2587
题目描述 Description

邪教喜欢在各种各样空间内跳。

现在,邪教来到了一个二维平面。在这个平面内,如果邪教当前跳到了(x,y),那么他下一步可以选择跳到以下4个点:(x-1,y), (x+1,y), (x,y-1), (x,y+1)。

而每当邪教到达一个点,他需要耗费一些体力,假设到达(x,y)需要耗费的体力用C(x,y)表示。

对于C(x,y),有以下几个性质:

1、若x=0或者y=0,则C(x,y)=1。

2、若x>0且y>0,则C(x,y)=C(x,y-1)+C(x-1,y)。

3、若x<0且y<0,则C(x,y)=无穷大。

现在,邪教想知道从(0,0)出发到(N,M),最少花费多少体力(到达(0,0)点花费的体力也需要被算入)。

由于答案可能很大,只需要输出答案对10^9+7取模的结果。

输入描述 Input Description

读入两个整数N,M,表示邪教想到达的点。

输出描述 Output Description

输出仅一个整数,表示邪教需要花费的最小体力对10^9+7取模的结果。

样例输入 Sample Input

1 2

样例输出 Sample Output

6

数据范围及提示 Data Size & Hint

对于10%的数据,满足N, M<=20;

对于30%的数据,满足N, M<=100;

对于60%的数据,满足min(N,M)<=100;

对于100%的数据,满足0<=N, M<=10^12,N*M<=10^12。

题解

很容易发现代价是组合数,然后贪心

\[ans=max(n,m)+\sum_{d=1}^{min(n,m)}C_{n+m}^{d}\]
\[ans=max(n,m)+C_{n+m+1}^{min(n,m)}\]

这个数据范围比较怪T T

用lucas的话极限数据在我的机子也要十几秒。。。

 

说点什么

提醒
avatar
王煜伟

黄学长,不用lacus能快一些,组合数可以直接O(min(n,m))求出,用高中数学里组合数的计算式。[(n-m+1)*(n-m)*…(一共min(n,m)项)]/m!,这样最大是10^6

233333333333333
233333333333333

MZoi

2
2

。。

北港不夏
北港不夏

黄学长你好,我知道带∑的算法怎么做,您是如何从题解里的第一个式子推到第二个的?

dick32165401
dick32165401

orz hty

QAQ
QAQ

可以用二项式的递推化简(高中刚刚学了组合数时候一般都会讲的例题。

1534531546
1534531546

具体数学里面有