Yukicoder No. 137 貯金箱の焦り

링크: https://yukicoder.me/problems/no/137

문제 요약:

$A_1$원, $A_2$원, $\cdots$, $A_N$원짜리 동전이 있습니다. 이 동전을 적당히 사용해서 합이 $M$원이 되도록 만드는 되는 경우의 수를 $1\,234\,567\,891$로 나눈 나머지를 구하세요. 하나 이상의 동전의 개수가 다른 경우 다른 경우로 셉니다.

 

제한

시간 제한: 5초 / 메모리 제한: 512MB

$1 \le N \le 50$

$1 \le M \le 10^{18}$

$1 \le A_1 < A_2 < \cdots < A_N \le 500$

 

풀이

$ \sum c_NA_N = M$이 되는 $0$ 이상의 수로 이루어진 $(c_1, \cdots, c_N)$ 순서쌍의 개수를 세는 문제입니다. $c_i$를 $2$진법으로 표현해서 $c_i = \sum (c_{j, i}2^j)$으로 표현하면, $\sum c_{j, i}(2^j A_i) = M$ 이 되는 $c_{j, i}$의 경우의 수를 찾는 문제입니다. 여기서 모든 $c_{j, i}$는 $0$ 혹은 $1$입니다.

 

이제 $N \log M$개 정도의 동전을 사용해서 $M$원을 만드는 경우의 수를 구하는 문제입니다. 이 문제 역시 직접 풀 수 없기 때문에, 다음과 $2^j A_i$꼴인 수가 홀수이기 위해서는 $j=0$이라는 관찰을 사용합시다.

 

일단 $A_1, A_2, \cdots, A_N$을 사용해서 우리가 모든 $0 \le x \le (\sum A_i)$에 대해 $x$원을 만드는 경우의 수를 구했다고 합니다.다음에 올 동전은 모두 가격이 짝수이고, $x$와 $M$의 홀짝성이 다르면 해당 경우는 절대로 $M$원을 만드는데 사용될 수 없습니다. 그래서 $M$이 홀수 혹은 짝수인지에 따라 $x$가 홀수 혹은 짝수인 것만 압축하고, 동전 가격을 절반으로 만들면 DP테이블과 이후의 동전 가격 역시 줄일 수 있습니다.

시간복잡도는 $\mathcal{O}((\sum A_i) \cdot N \cdot \log M)$입니다. (DP테이블의 길이가 절대 $2(\sum A_i) + 1$을 넘지 않습니다.)

 

코드: https://yukicoder.me/submissions/796065