一个人初始在（0， 0）， 想到（n, m)去， 没到一个格子， 花费的值为C(n, m）， 求最小值。
C(n, m)的定义为， 如果n==0||m==0, 则为1， 否则C(n, m) = C(n-1, m)+C(n, m-1)。
很容易看出来贪心的策略， 先横着或竖着走max(m, n）个格子，代价为max(m, n)+1， 然后在竖着或横着走，代价是一个组合数， C(n+m+1, min(n, m) )-1。 组合数用lucas算就好。
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <set> #include <string> #include <queue> #include <stack> #include <bitset> using namespace std; #define pb(x) push_back(x) #define ll long long #define mk(x, y) make_pair(x, y) #define lson l, m, rt<<1 #define mem(a) memset(a, 0, sizeof(a)) #define rson m+1, r, rt<<1|1 #define mem1(a) memset(a, -1, sizeof(a)) #define mem2(a) memset(a, 0x3f, sizeof(a)) #define rep(i, n, a) for(int i = a; i<n; i++) #define fi first #define se second typedef pair<int, int> pll; const double PI = acos(-1.0); const double eps = 1e-8; const ll mod = 1e9+7; const int inf = 1061109567; const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; ll pow(ll a, ll b) { ll ret = 1; while(b) { if(b&1LL) { ret = ret*a%mod; } a = a*a%mod; b >>= 1LL; } return ret; } ll C(ll n, ll k) { if(n<k) return 0; ll s1 = 1, s2 = 1; for(int i = 0; i<k; i++) { s1 = s1*(n-i)%mod; s2 = s2*(i+1)%mod; } return s1*pow(s2, mod-2)%mod; } ll lucas(ll a, ll b) { if(b == 0) return 1; return C(a%mod, b%mod)*lucas(a/mod, b/mod); } int main() { ll n, m; cin>>n>>m; ll ans = max(m, n); ans %= mod; ans += lucas(m+n+1, min(m, n)); ans %= mod; cout<<ans<<endl; return 0; }