AtCoder Beginner Contest 042 D - いろはちゃんとマス目 / Iroha and a Grid
- 問題
D - いろはちゃんとマス目 / Iroha and a Grid
- 解法
高校の数Aでよくあった問題。
(は素数)を求めるライブラリがあるとすぐ書ける。
#include <iostream> #include <vector> using namespace std; typedef long long int ll; const ll mod = 1e9+7; const ll INF = 1e9; const ll MAXN = 1e9; vector<ll> fact,inv; ll f(ll a,ll b, ll p) { if (b == 0) { return 1; }else if (b % 2 == 0) { ll d = f(a,b/2,p); return d * d % mod; }else { return a * f(a,b-1,p) % mod; } } void init(ll n) { fact.resize(n+1,1); inv.resize(n+1,1); for(int i = 2; i <= n; i++) { fact[i] = fact[i-1] * i % mod; } for(int i = 2; i <= n; i++) { inv[i] = f(fact[i],mod-2,mod) % mod; } } ll comb(ll n,ll k) { if (n < k) { return 0; } return (fact[n] * inv[k] % mod) * inv[n-k] % mod; } int main() { ll h,w,a,b; cin>>h>>w>>a>>b; init(h+w+1); ll ans = 0; for(int x = 1; x <= h-a; x++){ ans += comb(x-1+b-1,x-1) * comb(h-x+w-b-1,h-x); ans %= mod; } cout << ans << endl; return 0; }