테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== My뷰 꾸미기 ======

===== 풀이 =====
  * A>=B라고 하면, sum_1<=k<=B(C(A,k)*C(B,k)) 를 구해야 한다. sum_1<=k<=B(C(A,k)*C(B,B-k))로 바꾸면 [[ps:tutorial:이항계수#관련 공식과 정리들|반데르몽드 항등식]] 을 적용해서 C(A+B, B) - 1 로 바꿀 수 있다. 
    * 공식을 몰라도 조합론적으로 생각할수 있다. A+B 전체에서 B개를 뽑는다 => A글에서 k개가, B글에서 B-k개가 뽑힐텐데, A글에서는 뽑힌 것들을 기사로 올리고, B에서는 안뽑힌것들을 기사로 올리면, 같은수만큼 기사를 올리게 된다. B글에서만 k개가 다 뽑히는 한가지 경우만 제외해주면 되므로 결국 C(A+B, B) - 1
  * 전체 가짓수는 모든 관심분야에 대해서 가짓수의 곱을 구하면 된다. O(n)에 팩토리얼 % P를 전처리해두면, C(x,y) % P 는 O(1)에 구할수 있다. 그러면 관심분야 하나에 대해 O(1)에 구할수 있으므로 전체 가짓수는 O(N)에 구할수 있다. 총 시간복잡도는 O(N)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 25569. My뷰 꾸미기".

- Problem link: https://www.acmicpc.net/problem/25569
- Solution link: http://www.teferi.net/ps/problems/boj/25569

Tags: [combinatorics]
"""

import sys
from teflib import combinatorics

MOD = 10**9 + 7


def main():
    N = int(sys.stdin.readline())

    answer = 1
    cc = combinatorics.CombCalculator(MOD)
    for _ in range(N):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        large, small = (A, B) if A > B else (B, A)
        answer = answer * (cc.comb(large + small, small) - 1) % MOD

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#CombCalculator|teflib.combinatorics.CombCalculator]]
{{tag>BOJ ps:problems:boj:플래티넘_4}}