Boj 25569) My뷰 꾸미기

문제

백준 25569

설명

\[\binom{a+b}{r} = \sum_{i=0}^{i=r} \binom{a}{i}\binom{b}{r-i}\]

위 식은 간단하게 증명가능하다. a+b 크기에서 r 개를 꺼내는 방법은 a 에서 0 개 꺼내고 b 에서 r 개 꺼내는 경우와 a 에서 1 꺼내고 b 에서 r-1 개 꺼내고 …. . 다시말해 식 그대로이다.

이 식을 문제의 조건에 따라 조금만 변형하면 다음과 같다.

\[\binom{a+b}{a} = \sum_{i=0}^{i=a} \binom{a}{i}\binom{b}{a-i} = \sum_{i=0}^{i=a} \binom{a}{a-i}\binom{b}{a-i}\]

이는 우리가 풀어야 하는 식과 동일하다. 따라서 상수 시간에 쿼리 하나를 처리할 수 있다.

팁으로 Factorial 전처리를 위해 점화식을 사용했다면 똑같이 Mod Inv 도 점화식으로 처리할 수 있다. 가장 마지막의 Factorial 만 Mod Inv 를 취하고 뒤에는 역순으로 곱해나가면 된다.

시간 복잡도

O(\(\mathrm{N} \log{\mathrm{N}}\))

코드

using ll = long long;
const int MOD = 1e9 + 7;
int64_t ModInv(int t)
{
	int idx = MOD - 2; int64_t base = t, res = 1;
	while (idx)
	{
		if (idx & 1)  res = (res * base) % MOD;
		base = (base * base) % MOD;
		idx >>= 1;
	}
	return res;
}


ll fact[600001], fact_inv[300001];
inline ll C(int a, int b) { return (fact[a] * fact_inv[a - b] % MOD) * fact_inv[b] % MOD; }

int main()
{
	fact[0] = 1;
	for (int i = 1; i <= 600001; i++)
		fact[i] = fact[i - 1] * i % MOD;
	fact_inv[300000] = ModInv(fact[300000]);
	for (int i = 300000; i > 0; i--)
		fact_inv[i-1] = fact_inv[i] * i % MOD;
		
	int n; cin >> n;
	int res = 1;
	for (int i = 0; i < n; i++)
	{
		int a, b; cin >> a >> b;
		res = (C(a+b, a)-1) * res % MOD;
	}
	cout << res;
}