「CODEVS1515」跳

2015年1月9日3,8417

题目描述 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

数据范围及提示 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的话极限数据在我的机子也要十几秒。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define P 1000000007
#define ll long long
using namespace std;
inline ll read()
{
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
ll n,m;
ll qpow(ll a,ll b)
{
	ll ans=1;
	for(ll i=b;i;i>>=1,a=(a*a)%P)
		if(i&1)ans=ans*a%P;
	return ans;
}
ll C(ll a,ll b)
{
	if(b>a)return 0;
	if(b>a-b)b=a-b;
	ll s1=1,s2=1;
	for(ll i=1;i<=b;i++)
	{
		s1=s1*(a-i+1)%P;
		s2=s2*i%P;
	}
	return s1*qpow(s2,P-2)%P;
}
ll lucas(ll a,ll b)
{
	return C(a/P,b/P)*C(a%P,b%P);
}
int main()
{
	n=read();m=read();
	printf("%lld",(lucas(n+m+1,min(n,m))+max(n,m))%P);
	return 0;
}