JUST CODE IT通过本文主要向大家介绍了51nod,51nod官网,51nod登录,51nod算法,51nod 1284等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
题目链接
长知识了。。。
(a+b)%mod=(a%mod+b%mod)%mod
a*b%mod=(a%mod*b%mod)%mod
a/b%mod =a*(b^(mod-2))%mod;
然后开干。。
第一种排列组合：
这个在高中基本都做过的题目，
从1，1到n，m一共朝下走n-1步，朝右走m-1步
总共n+m-2，然后选一条路n-1或者m-1就是结果
C（n+m-2,n-1）
因为结果要%mod，就要用到第三个公式
其中b^(mod-2)很明显的快速幂（前面才做到的题目）
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const long long mod=1000000000+7;
long long sum(int x,int num){
long long fz=1;
while(num--)
fz*=x--,fz%=mod;
return fz;
}
long long jc(int x){
long long sum=1;
while(x) sum*=x--,sum%=mod;
return sum;
}
long long ksm(long long x){
long long mm=mod-2;
long long sum=1,temp=x;
while(mm){
if(mm&1) sum=sum*temp%mod;
temp*=temp;
temp%=mod;
mm=mm>>1;
}
return sum%mod;
}
int main(){
int n,m;
cin>>n>>m;
int minn=(n,m);
int fz=jc(n-1);
int su=sum(n+m-2,n-1);
/*
(x/y) %mod =x*(y^(mod-2))%mod;
*/
long long chshu=ksm(fz);
//cout<<fz<<" "<<su<<" "<<chshu<<endl;
cout<<su*chshu%mod;
return 0;
}
第二种dp：
这题类似于小兔子跳楼梯，每一个点都是由上面或者左面的移动一次得到
dp[i][j]=(dp[i-1][j]%mod+dp[i][j-1]%mod)%mod
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const long mod=1000000000+7;
int main(){
int n,m;
cin>>n>>m;
int a[1001][1001];
a[1][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i==1&&j==1) continue;
a[i][j]=(a[i-1][j]%mod+a[i][j-1]%mod)%mod;
}
}
cout<<a[n][m];
return 0;
}