51Nod 1627 瞬间移动 —

51Nod 1627 瞬间移动 —— 组合数学

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1627

1627 瞬间移动

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第n行第m列的格子有几种方案，答案对1000000007取模。

Input

单组测试数据。
两个整数n,m（2<=n,m<=100000）

Output

一个整数表示答案。

Input示例

4 5

Output示例

题解：

1.如果去除掉起点和终点，那么就是对中间的矩形进行统计。则首先 n -= 2， m -= 2。

2. 可知里边的矩形最多只能有 min(n,m)个足迹，假设m = min(n,m)，即最多只能有m个足迹。

3.根据以上两点，可以枚举矩形里足迹的个数i，然后再为这i个足迹分配横、纵坐标，总共有 C(n,i)*C(m,i)种情况，则最终答案为：∑C(n,i)*C(m,i) ， 0<=i<=m 。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXM = 1e5+10;
18 const int MAXN = 2e5+10;
19 
20 LL qpow(LL x, LL y)
21 {
22     LL s = 1;
23     while(y)
24     {
25         if(y&1) s = (s*x)%MOD;
26         x = (x*x)%MOD;
27         y >>= 1;
28     }
29     return s;
30 }
31 
32 LL A[MAXN], inv[MAXN];
33 LL C(LL n, LL m)
34 {
35     if(n<m) return 0;
36     return (((A[n]*inv[n-m])%MOD)*inv[m])%MOD;
37 }
38 
39 void init()
40 {
41     A[0] = inv[0] = 1;
42     for(int i = 1; i<MAXN; i++)
43     {
44         A[i] = i*A[i-1]%MOD;
45         inv[i] = qpow(A[i], MOD-2);
46     }
47 }
48 
49 int main()
50 {
51     init();
52     LL n, m;
53     while(scanf("%lld%lld",&n,&m)!=EOF)
54     {
55         n -= 2; m -= 2; //去掉起始点和终点，只对里边的矩形进行统计
56         if(n<m) swap(n,m);
57         LL ans = 0;    
58         for(int i = 0; i<=m; i++)     //里边的矩形最多只能有min(n,m)个“足迹”,即最多只能走min(n,m)+1步
59             ans = (ans+C(m,i)*C(n,i)%MOD)%MOD;  //如果里边有i个足迹，则为这i个足迹选择横坐标、纵坐标
60         printf("%lld
", ans);
61     }
62 }

View Code