首页 > 代码库 > [51nod1119]机器人走方格V2
[51nod1119]机器人走方格V2
解题关键：
1、此题用dp的方法可以看出，dp矩阵为杨辉三角，通过总结，可以得出 答案的解为$C_{n + m - 2}^{n - 1}$
2、此题可用组合数学的思想考虑，总的步数一共有$n+m-2$步，在这所有的步数中，需要选择向下走的步数的位置，由此可得，答案的解为：$C_{n + m - 2}^{n - 1}$
此题即可转化为大组合数取模问题；
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod=1e9+7; 5 ll mod_pow(ll x,ll n,ll p){ 6 ll res=1; 7 while(n){ 8 if(n&1) res=res*x%p; 9 x=x*x%p;10 n>>=1;11 }12 return res;13 }14 ll comb(ll n,ll m,ll p){15 if(n==m) return 1;16 if(n<m) return 0;17 if(m>n-m) m=n-m;18 19 ll tn=1,tm=1;20 while(m){21 tn=tn*n%p;22 tm=tm*m%p;23 n--,m--;24 }25 return (tn*mod_pow(tm,p-2,p)+mod)%mod;26 }27 int main(){28 int n,m;29 cin>>n>>m;30 ll ans=comb(n+m-2,n-1,mod);31 cout<<ans<<endl;32 return 0;33 }
如下为dp的解法
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod=1e9+7; 5 int dp[1002][1002]; 6 int main(){ 7 int n,m; 8 cin>>n>>m; 9 for(int i=0;i<=1000;i++){10 dp[1][i]=dp[i][1]=1;11 }12 for(int i=2;i<=m;i++){13 for(int j=2;j<=n;j++){14 dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;15 }16 }17 cout<<dp[m][n]<<endl;18 }
[51nod1119]机器人走方格V2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。