#1492 합

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

 

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

 

파스칼의 삼각형

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

이항 계수는 n개에서 r개를 고르는 경우의 수를 나타내는 것으로 ${}_n{C}_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$을 구하기 위한 방법입니다.  이를 위해서는 계차를 구하는 방법을 이용했습니다.

 

예를 들어서 $su{m}_{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=4n^3-6n^2+4n-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 ) 함수를 이용하여 역수를 구한 후 곱했습니다.

 

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