AtCoder Beginner Contest 034 C - 経路

問題

C: 経路 - AtCoder Beginner Contest 034 | AtCoder

解法

二項係数を高速に求めるやつ。
DPで求めるのは間に合わないので、階乗とか出てくる一般項を計算する。
逆元の中で繰り返し二乗法を使うと階乗が一番重くなって、

実装

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int MOD = 1000000007;
const int MAX_W = 100000, MAX_H = 100000;
 
int Pow(int x, int n)
{
	if (n == 0) return 1;
	return Pow(x*x % MOD, n/2)*((n&1) ? x : 1) % MOD;
}
 
int Inverse(int x)
{
	return Pow(x, MOD - 2);
}
 
int fac[MAX_W + MAX_H + 1] = {-2};
int Factorial(int n)
{
	if (fac[0] == -2) fill(fac, fac + MAX_W + MAX_H + 1, -1);
	if (fac[n] != -1) return fac[n];
	if (n == 0) return 1;
	return fac[n] = Factorial(n - 1)*n % MOD;
}
 
int Combination(int n, int k)
{
	return (Factorial(n) * Inverse(Factorial(n - k)) % MOD)*Inverse(Factorial(k)) % MOD;
}
 
int W, H;
 
signed main()
{
	cin >> W >> H;
	printf("%lld\n", Combination(W + H - 2, W - 1));
	return 0;
}