#1492 합

이번 문제는 Platinum II로 꽤 높게 책정된 문제입니다.

 

문제 자체는 상당히 쉽습니다.  1부터 n까지 \(n^k\)의 합을 구하라는 문제입니다.

 

파스칼의 삼각형

여기서는 파스칼의 삼각형과 연관된 이항계수에 대해서 먼저 알고 있어야 합니다.

이항 계수는 n개에서 r개를 고르는 경우의 수를 나타내는 것으로 \( _nC_r \)로 표현됩니다.  이항 계수를 바로 구할 수도 있겠지만, 저는 프로그램에서는 파스칼의 삼각형을 이용했습니다.  n이 최대 51까지밖에 안 되기되문에 크게 문제가 없습니다.  더 크다면 이항 계수를 구하기 위해서는 별도의 방법을 이용해야 합니다.

 

다음 코드는 파스칼 삼각형을 이용해서 주어진 n에 대해서 이항계수를 구하는 것입니다.  사실 그냥 for 루프를 이용해서 작성할 수 있겠지만, 여기서는 동적 계획법을 이용했습니다.

 

MOD = 1000000007
pascal = [ None ]*52
pascal[0] = (1,)

def getPascal(n):
    if pascal[n] != None: return pascal[n]
    x = getPascal(n-1)
    v = [1, ]
    for i in range(n-1):
        v.append((x[i]+x[i+1])%MOD)
    v.append(1)
    pascal[n] =  tuple(v)
    return pascal[n]

 

파스칼 삼각형의 한줄을 구하는 프로그램이자, \( (x+1)^n \)의 이항 계수들입니다.  예를 들면 getPascal(2)를 실행하면 (1, 2, 1)을 얻게 됩니다.  이 의미를 \( (x+1)^2 = x^2 + 2x + 1 \)을 의미합니다.  파스칼 삼각형은 좌우 대칭이므로 x의 거듭제곱을 역으로 배치해도 됩니다.

 

다음은 \( \sum_{x=1}^{n} {x^k} \)을 구하기 위한 방법입니다.  이를 위해서는 계차를 구하는 방법을 이용했습니다.

 

예를 들어서 \( sum_{x=1}^{n} {x^3} \) 를 구해보도롤 할께요.  이미 \( \sum_{x=1}^{n} {x^2} = n/6 + n^2/2 + n^3/3 \) 과 \( \sum_{x=1}^{n} {x} = n/2 + n^2/2 \) 임을 알고 있다고 하죠.

 

\[ n^4 - (n-1)^4 = 4 n^3 - 6 n^2 + 4 n - 1 \]

을 얻을 수 있습니다. 

 

\[ \sum_{k=1}^{n} { k^4 - (k-1)^4 } = n^4 - (n-1)^4 + (n-1)^4 - (n-2)^4 + ... + 1^4 - 0^4 = n^4 \]

인 것에 착안하여 위의 식에 양벽에 \( \sum \)을 취합니다.

 

\[ n^4 = 4 \sum k^3 - 6 \sum k^2 + 4 \sum k - \sum 1 \]

\[ 4 \sum k^3 = n^4  + 6 \sum k^2 - 4 \sum k + \sum 1 \]

을 얻게 됩니다.

 

그러면 우리가 이미 알고 있다고 가정한 것을 위에 적용합니다.

\[ 4 \sum k^3 = n^4  + 6 (n/6 + n^2/2 + n^3/3) - 4 (n/2 + n^2/2) + n \]

\[ 4 \sum k^3 = n^4  + (n + 3n^2 + 2n^3) - (2n + 2n^2) + n \]

\[ 4 \sum k^3 = n^2 + 2n^3  + n^4 = n^2 (n+1)^2  \]

을 얻게 됩니다.  최종적으로는 우리가 잘 알고 있는 형태로

\[ \sum k^3 = \frac {n^2 (n+1)^2}{4}  \]

가 되는 것이죠.

 

재귀적으로 동적 계획법을 잘 이용해서 프로그램을 작성하면 됩니다.

 

숫자가 커지기 때문에 나누기는 파이썬의 pow( n, -1, 1,000,000,007 ) 함수를 이용하여 역수를 구한 후 곱했습니다.

 

프로그램을 작성하고 보니, 꽤 내용이 커지게 되네요.