짝수 행 세기

• 문제에서는 인풋으로 테이블이 들어오지만, 사실 테이블 자체는 필요 없고, 각 열에 1이 몇 개씩 있는지만 알면 된다. 굳이 의미도 없는데 테이블 전체를 인풋으로 준 것은 일부러 헷갈리게 하려 한건가..
• DP[c][e] 를 c열까지 테이블을 채웠을 때 짝수 행이 e개가 되는 방법의 갯수라고 정의하자.
• 이제 c열까지 테이블을 짝수 행이 e개가 있도록 채웠을 때, 여기에 c+1열을 채우는 상황을 생각하자. c+1열에 채울 수 있는 1의 갯수가 o개라고 하면, o개중 x개를 짝수 행에 채우고, y개를 홀수 행에 채울 수 있다 (x+y=o). 그러면 e개의 짝수 행 중에서 x개는 홀수 행이 되고, (R-e)개의 홀수 행 중에서 y개는 짝수 행으로 바뀐다. 따라서 짝수 행의 갯수는 e-x+y가 된다.
• 이것을 정리하면 c열까지 짝수행이 e개인 상태에서, c+1열까지의 짝수행이 e-x+y가 되는 방법의 수 f(c+1, e-x+y, e)는 {c열까지 짝수행이 e개인 상태의 수} * {e개의 짝수 행중 x개를 고르는 방법의 수} * {(R-e)개의 홀수 행중 y개를 고르는 방법의 수}가 된다.
  • $ f(c+1, e-x+y, e) = DP[c][e]*C(e,x)*C(R-e,y) $
• 그리고 $ DP[c+1][e-x+y] = \sum_e{f(c+1,e-x+y,e)} = \sum_e{DP[c][e]\times C(e,x) \times C(R-e,y)} $ 가 된다.
• 하나의 셀을 업데이트 하는데 O(R)*2 개의 이항계수 C(n,k) 계산이 필요하다. C(n,k)는 이항 계수 (Binomial Coefficient)에서 설명한 알고리즘을 사용해서 O(R)의 전처리를 하면, O(1)에 구할 수 있고, 따라서 하나의 셀을 업데이트 하는것은 O(R)에 가능하다. 모든 테이블을 채우는 것은 총 C*R개의 셀을 계산해야 해야하므로, O(C*R*R)이 걸린다. 이항계수 계산을 위한 전처리 O(R)을 포함해도 전체 시간 복잡도는 O(C*R^2)이다

"""Solution code for "Programmers 68647. 짝수 행 세기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/68647
- Solution link: http://www.teferi.net/ps/problems/programmers/68647
"""

from teflib import combinatorics

MOD = 10**7 + 19


def solution(a):
    row_count = len(a)
    col_count = len(a[0])
    comb_table = combinatorics.CombTable(row_count + 1, MOD)
    dp_cur = [0] * row_count + [1]
    for c in range(col_count):
        dp_cur, dp_prev = [0] * (row_count + 1), dp_cur
        one_count = sum(row[c] for row in a)
        for x in range(one_count + 1):
            y = one_count - x
            for even_row_count in range(x, row_count - y + 1):
                odd_row_count = row_count - even_row_count
                new_even_row_count = even_row_count - x + y
                dp_cur[new_even_row_count] += (
                    dp_prev[even_row_count] *
                    comb_table.get(even_row_count, x) *
                    comb_table.get(odd_row_count, y))
        for i in range(row_count + 1):
            dp_cur[i] %= MOD

    return dp_cur[row_count]

• Dependency: teflib.combinatorics.CombTable