CodeVs1515 跳

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

数学问题组合数 lucas定理

看到那个C的表达式就觉得和组合数有关系，于是欢快地打了个小表，发现——和组合数没多大关系

以左上角为顶点，每个位置的值以杨辉三角形式增加。根据这一性质可以想出一个贪心方法：只走直线，先贴着边走到目标点所在的行/列，然后直走过去。

于是ans=max(n,m)+ Σ C(n+m,d) (1<=d<=min(n,m)) ← C是组合数

题解说后面那个ΣC 就等于C(n+m+1,min(n,m))

看到别的题解写了lucas定理，自己想了想觉得可以暴力推过去。N*M<=10^12，根据C(n,m)=c(n,n-m)的性质可知公式求组合数最多循环10^6次，可以接受。

确实可以推过去，然而WA了几个点，原因是这样算，乘数爆longlong了。

又加了个快速乘就过了。

下附lucas定理写法：

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 #define LL long long

 using namespace std;

 const int mod=1e9+;

 LL ksmul(LL a,LL b){

     a%=mod;b%=mod;LL res=;

     while(b){

         if(b&){res+=a;if(res>mod)res-=mod;}

         a=(a<<)%mod;

         b>>=;

     }

     return res;

 }

 LL ksm(LL a,LL k){

     LL res=;

     while(k){

         if(k&)res=ksmul(res,a);

         a=ksmul(a,a);

         k>>=;

     }

     return res;

 }

 LL solve(LL n,LL m){

     m=max(m,n-m);

     LL res=,inv=;

     for(LL i=m+;i<=n;i++){

         res=ksmul(res,i);

         inv=ksmul(inv,i-m);

 //        printf("res:%lld inv:%lld\n",res,inv);

     }

     inv=ksm(inv,mod-)%mod;

     res=ksmul(res,inv);

     return res;

 }

 LL n,m,ans=;

 int main(){

     int i,j;

     scanf("%lld%lld",&n,&m);

     if(n<m)swap(n,m);

     ans+=n%mod;

     (ans+=solve(n+m+,m))%=mod;

     printf("%lld\n",ans);

     return ;

 }

lucas还是快一点

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 #define LL long long

 using namespace std;

 const int mod=1e9+;

 LL ksm(LL a,LL k){

     LL res=;

     while(k){

         if(k&)res=(res*a)%mod;

         a=(a*a)%mod;

         k>>=;

     }

     return res;

 }

 LL clc(LL n,LL m){

     if(n<m)return ;

     m=min(m,n-m);

     LL res=,inv=;

     for(LL i=;i<=m;i++){

         res=res*(n-i+)%mod;

         inv=inv*i%mod;

     }

     res=res*(ksm(inv,mod-))%mod;

     return res;

 }

 LL lucas(LL a,LL b){

     if(!b)return ;

     return clc(a%mod,b%mod)*(lucas(a/mod,b/mod)%mod)%mod;

 }

 LL n,m,ans=;

 int main(){

     int i,j;

     scanf("%lld%lld",&n,&m);

     if(n<m)swap(n,m);

     ans+=n%mod;

     (ans+=lucas(n+m+,m))%=mod;

     printf("%lld\n",ans);

     return ;

 }

lucas

Lucas

CodeVs1515 跳