My뷰 꾸미기

• A>=B라고 하면, sum_1⇐k⇐B(C(A,k)*C(B,k)) 를 구해야 한다. sum_1⇐k⇐B(C(A,k)*C(B,B-k))로 바꾸면 반데르몽드 항등식 을 적용해서 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)

"""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()

• Dependency: teflib.combinatorics.CombCalculator