합 구하기

Summary:

$S(0, n) = n$

$S(k, n) = S(k-1, 1) + S(k-1, 2) + \dots + S(k-1, n)$

$k,n$이 주어질때 $S(k,n)$을 구하는 문제이다

Solution:

k는 50으로 작은 반면, n은 10억으로 너무 크다.

10억은 $O(N)$으로도 불가능하기 때문에 dp를 이용해 풀수도 없다.

$k$가 작은 점을 이용해 $k \times k$ 행렬을 이용해서 계산한다면

\[\begin{pmatrix} 1 \\ (0,n) \\ (1,n) \\ \dots \\ (k,n) \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 &0 &\dots &0 \\ 1 &1 &0 &\dots &0 \\ 1 &1 &1 &\dots &0 \\ \dots \\ 1 &1 &1 &\dots &1 \\ \end{pmatrix} \begin{pmatrix} 1 \\ (0,n-1) \\ (1,n-1) \\ \dots \\ (k,n-1) \\ \end{pmatrix}\]

이고,

\[\begin{pmatrix} 1 \\ (0,n) \\ (1,n) \\ \dots \\ (k,n) \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 &0 &\dots &0 \\ 1 &1 &0 &\dots &0 \\ 1 &1 &1 &\dots &0 \\ \dots \\ 1 &1 &1 &\dots &1 \\ \end{pmatrix} ^{n-1} \begin{pmatrix} 1 \\ 1 \\ 1 \\ \dots \\ 1 \\ \end{pmatrix}\]

이렇게 하면 되기 때문에 $k\times k$행렬의 거듭제곱을 로그만에 계산하면 $O(k^3logn)$의 시간복잡도로 해결할수 있다.