首页 > 代码库 > 【费马小定理】BZOJ3260-跳
【费马小定理】BZOJ3260-跳
【题目大意】
一个二维平面。在这个平面内，如果当前跳到了(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取模的结果。
【思路】
组合数^ ^
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<map> 5 #define ll long long 6 using namespace std; 7 const int mod=1e9+7; 8 ll n,m; 9 10 ll pow(ll x,ll k)11 {12 ll ret=1;13 for(int i=k;i;i>>=1,x=x*x%mod)14 if(i&1) ret=ret*x%mod;15 return ret;16 }17 18 19 void solve()20 {21 scanf("%lld%lld",&n,&m);22 if(n>m) swap(n,m);23 m%=mod;24 ll ans=m+1;25 26 ll x=1;27 for(int i=1;i<=n;i++)28 {29 x=(x*(m+i))%mod;30 x=(x*pow(i,mod-2))%mod;31 ans=(ans+x)%mod;32 }33 printf("%lld\n",ans);34 35 }36 37 int main()38 {39 solve();40 return 0;41 }
【费马小定理】BZOJ3260-跳
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。