돌무더기의 정상화

• 우선 가져가는 순서에 대한 규칙은 무시하고 생각해보자. 어떤 순서로든 둘이 돌을 나눠 가졌을때, 가져간 돌의 개수가 같아지게 하는 방법이 존재하는가만 놓고 보면, 전형적인 2-partition 문제이다. Subset sum 문제의 대표유형이고 냅색 DP로 풀수 있다. 가져가는 순서를 고려하지 않는다면, 둘이 가져간 돌의 개수가 같아지게 하는 방법의 개수를 구하는 것으로 확장해도 여전히 전형적인 냅색DP 문제이다.
• 가져가는 순서를 고려해서 방법의 수를 구하기 위해서는 관찰이 필요하다. 증명없이 관찰을 나열하면
  • 먼저, 희원이가 가져가야하는 무더기들이 정해졌을때, 게임 규칙을 위배하지 않고 희원이가 그 무더기들을 가져갈수 있는 방법은 항상 존재한다.
  • 나아가면, 희원이가 그 무더기들을 어떤 순서로 가져가려고 하든지, 게임 규칙을 위배하지 않고 그 무더기들을 가져갈수 있는 방법도 항상 존재한다.
  • 더 나아가면, 희원이가 그 무더기들을 특정 순서로 가져가고, 채원이가 나머지 무더기들을 특정 순서로 가져가려고 할때에도, 규칙을 위배하지 않고 무더기들을 가져가는 방법은 항상 존재한다. 그리고 그 방법은 유일하다.
  • 이걸 정리하면, 희원이가 자신의 무더기들을 가져가는 순서와, 채원이가 자신의 무더기들을 가져가는 순서가 고정되면, 전체 무더기를 가져가는 순서가 유일하게 나온다. 즉, 희원이가 가져가야 할 무더기의 개수가 l개, 채원이가 가져갈 무더기의 개수가 N-l개라면 이것을 가져갈 수 있는 전체 순서 (=순열)의 개수는 l! * (N-1)! 로 계산할 수 있다
• 이제 필요한 것은, $ {A_1, A_2, ..., A_N} $ 의 부분집합중에서 합이 $ (/sum A_i) / 2 $ 가 되는 부분집합의 개수를, 부분집합의 크기별로 구분해서 세어주는 것 뿐이다. 이것은 기본적인 냅색DP의 프레임에서 저장해야 하는 값에 {크기 : 갯수} 의 딕셔너리를 저장해주기만 하면 된다. 계산이 끝난 후에는 위에서 설명한 방법으로 팩토리얼을 계산해서 카운팅을 해주면 된다.
• DP 테이블의 크기는 N*W 이고, 각 셀에는 딕셔너리가 있으므로 업데이트 하는데 O(N)이 걸린다. 따라서 총 시간복잡도는 O(N^2*W) = O(N^2 * N*max(A)) = O(N^3 * max(A)) 가 된다.

"""Solution code for "BOJ 32382. 돌무더기의 정상화".

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

Tags: [knapsack]
"""

import collections

MOD = 1_000_000_007


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    if (sum_a := sum(A)) % 2 != 0:
        print('0')
        return

    target = sum_a // 2
    count_by_len = [collections.defaultdict(int) for _ in range(target + 1)]
    count_by_len[0][0] = 1
    for a_i in A:
        for w in reversed(range(a_i, target + 1)):
            for l, count in count_by_len[w - a_i].items():
                count_by_len[w][l + 1] += count

    fact = [v := 1] + [(v := v * i % MOD) for i in range(1, N + 1)]
    answer = (
        sum(
            fact[l] * fact[N - l] * count
            for l, count in count_by_len[target].items()
        )
        % MOD
    )
    print(answer)


if __name__ == '__main__':
    main()