51nod 1118 机器人走方格
动规(简单)
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> using namespace std; #define LL long long #define INF 0x3f3f3f3f #define PI acos(-1.0) #define E 2.71828 #define MOD 1000000007 #define N 1010 LL dp[N][N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(i == j && i == 1) dp[i][j] = 1; else dp[i][j] = (dp[i-1][j]+dp[i][j-1])%MOD; } } printf("%lld\n",dp[n][m]); return 0; }组合数 从m+n-2个不同元素中取出n-1个元素的所有组合的个数.（用到乘法逆元）
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> using namespace std; #define LL long long #define INF 0x3f3f3f3f #define PI acos(-1.0) #define E 2.71828 #define MOD 1000000007 #define N 200 LL exgcd(LL a,LL b,LL &x,LL &y) { if(b == 0) { x = 1; y = 0; return a; } LL d = exgcd(b,a%b,x,y); LL t = x; x = y; y = t - a/b*y; return d; } int main() { int n,m; scanf("%d%d",&n,&m); LL fenzi = 1; for(int i = m+n-2,j = 1; j <= n-1; i--,j++) fenzi = (fenzi * i)%MOD; for(int i = 1; i <= n-1; i++) { LL x, y; exgcd(i,MOD,x,y); x = (x % MOD + MOD)%MOD; fenzi = (fenzi*x)%MOD; } printf("%lld\n",fenzi); return 0; }