AT1974 [ARC058B] いろはちゃんとマス目 / Iroha and a Grid

Grid"/>

AT1974 [ARC058B] いろはちゃんとマス目 / Iroha and a Grid

根据简单的组合数可以知道从 ( a , b ) (a,b) (a,b)到 ( x , y ) (x,y) (x,y)的路径方案数是
( x − a + y − b x − a ) \binom{x-a+y-b}{x-a} (x−ax−a+y−b​)

然后枚举中间点，把两遍乘起来求和即可

code:

#include<bits/stdc++.h>
#define N 200500
#define ll long long
#define mod 1000000007
using namespace std;
ll qpow(ll x, ll y) {ll ret = 1;for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;return ret;
}
ll fac[N], ifac[N];
void init(int n) {fac[0] = 1;for(int i = 1; i <= n; i ++) fac[i] = fac[i - 1] * i % mod;ifac[n] = qpow(fac[n], mod - 2);for(int i = n - 1; i >= 0; i --) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
ll C(int n, int m) {return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
ll calc(int x, int y, int xx, int yy) {return C(xx + yy - x - y, xx - x);
}
int n, m, a, b;
int main() {scanf("%d%d%d%d", &n, &m, &a, &b);init(n + m);ll ans = 0;for(int i = 1; i <= n - a; i ++)ans += calc(1, 1, i, b) * calc(i, b + 1, n, m) % mod, ans %= mod;printf("%lld", ans);return 0;
}