모든 부분집합 원소의 곱의 합을 구하는 공식이 있다고?

1. 문제

 

9375번: 패션왕 신해빈 (acmicpc.net)

9375번: 패션왕 신해빈

 

2. 풀이

 

경우의 수가 바로 안나오기는 한디... 경우를 나눠서 생각해보면 

 

hat headgear
sunglasses eyewear
turban headgear

 

headgear에 2가지 있고 eyewear에 1가지 있는데..

 

headgear에서 1가지를 뽑는 경우의 수 = 2가지 + eyewear에서 1가지 뽑는 경우의 수 1가지 = 3가지

 

headgear에서 1가지, eyewear에서 1가지 뽑는 경우의 수 = 2*1 = 2가지

 

= 총 3+2 = 5가지

 

사실 조금 생각해보면.. 옷의 각 종류별로 a1,a2,a3...,an이 있다고 할때 집합 {a1,a2,...,an}의 모든 부분집합

 

{a1}, {a2}, ... {a1,a2,...,an}의 원소들의 곱의 합이 정답이다.

 

위 경우도 {1,2}의 부분집합 {1}, {2}, {1,2}의 원소들의 곱의 합 1 + 2 + 1*2 = 5가 된다

 

근데 부분집합 구하는 법이 생각 안나서..

 

https://deepdata.tistory.com/428

바이너리 카운팅을 이용한 부분집합 구현과 재귀함수를 이용한 조합 구현하기

 

찾아봐서 부분집합 구해서 원소들의 곱의 합 구해도... 시간초과더라

 

당연한게 최대 30가지니까 최악의 경우 2^30 = 약 10억 정도라 1초안에 될리가 없지

 

from sys import stdin

T = int(stdin.readline())

for _ in range(T):
    
    n = int(stdin.readline())

    clothes = {}

    for _ in range(n):
        
        a,b = stdin.readline().rstrip().split()

        clothes[b] = clothes.get(b,0) + 1
    
    answer = 0

    all = list(clothes.keys())

    m = len(all)

    for i in range(1 << m):
        
        partial = []

        for j in range(m):
            
            if i &(1 << j):

                partial.append(all[j])

        if len(partial) == 0:
            
            continue
            
        count = 1

        for p in partial:
            
            count *= clothes[p]

        answer += count
    
    print(answer)

 

3. 모든 부분집합의 원소들의 곱의 합

 

사실 다음과 같은 공식?이 있는데

 

{a1,a2,...,an}의 원소가 k개인 부분집합의 곱의 합을 $S_{k}$라고 한다면..

 

$$(x+a_{1})(x+a_{2})...(x+a_{n}) = x^{n} + S_{1}x^{n-1} + ... + S_{n}$$

 

수학적 귀납법으로 보일 수 있을 것 같기는 한디.. 간단하게 증명해보자면..

 

n = 1이면 $S_{1} = a_{1}$이므로 자명

 

자연수 k에 대하여 n = k에서 성립한다고 가정하면.. n = k+1에서 성립하는가?

 

$(x+a_{1})..(x+a_{k}) = x^{k}+S_{1}x^{k-1}+...+S_{k}$

 

양변에 $x+a_{k+1}$을 곱하면..

 

$(x^{k} + S_{1}x^{k-1}+...+S_{k})(x+a_{k+1}) = x^{k+1} + S_{1}x^{k} + ... + S_{k}x + a_{k+1}x^{k} + a_{k+1}S_{1}x^{k-1}+...+a_{k+1}S_{k}$

 

$x^{k+1} + (S_{1}+a_{k+1})x^{k} + ... +(S_{2}+a_{k+1}S_{1})x^{k-1}+...+a_{k+1}S_{k}$

 

$S_{1} + a_{k+1} = a_{1}+...a_{k} + a_{k+1} = S_{1}$으로 원소가 1개인 부분집합의 원소들의 곱의 합

 

$S_{2} + a_{k+1}S_{1} = \sum_{i ≠ j}a_{i}a_{j} + \sum_{i = k+1, j ≠ k+1}a_{i}a_{j} = S_{2}$으로..

 

원소가 2개인 부분집합의 원소들의 곱의 합

 

...

 

$a_{k+1}S_{k} = a_{k+1}a_{1}a_{2}...a_{k} = S_{k+1}$로 원소가 k+1개인 부분집합의 원소들의 곱의 합

 

그래서..

 

$(x^{k} + S_{1}x^{k-1}+...+S_{k})(x+a_{k+1}) = x^{k+1} + S_{1}x^{k} + ... + S_{2}x^{k-1}+...+S_{k+1}$

 

그러므로 n = k+1에서도 성립한다

 

아무튼 위 사실에 입각하면 구하고자 하는 값은 $S_{1} + S_{2} + ... + S_{n}$

 

x = 1을 대입해도 성립하는 항등식이므로.. $(1+a_{1})(1+a_{2})...(1+a_{n}) = 1 + S_{1} + ... + S_{n}$

 

그러므로 옷의 종류들의 개수 $a_{i}$를 저장해두고, for문으로 순회하면서 1을 더한채로 누적곱을 한 다음

 

마지막에 1을 빼준다면 O(N)에 문제를 해결할 수 있을 것이다.

 

from sys import stdin

T = int(stdin.readline())

for _ in range(T):
    
    n = int(stdin.readline())

    clothes = {}

    for _ in range(n):
        
        a,b = stdin.readline().rstrip().split()

        clothes[b] = clothes.get(b,0) + 1
    
    answer = 1

    for k,v in clothes.items():
        
        answer *= (v+1)
    
    print(answer - 1)