【codevs1515】跳

2015年1月9日1,9087
题目描述 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的话极限数据在我的机子也要十几秒。。。

 

  • 北港不夏2016年3月16日 下午9:23 回复

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

    #1  
    • 15345315462016年3月17日 下午1:59 回复

      具体数学里面有

      #11
    • QAQ2016年3月17日 下午3:11 回复

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

      #11
    • dick321654012016年3月18日 上午10:09 回复

      orz hty

      #11
  • 22016年3月21日 下午5:29 回复

    。。

    #2  
  • 2333333333333332016年3月21日 下午5:30 回复

    MZoi

    #3  
  • 王煜伟2017年2月28日 下午5:35 回复

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

    #4