H. Polynomial BOJ 11500

 문제 설명 :

  어떤 함수 f(k)를 아래와 같이 정의한다. 

 이 때 우리는 f에 관한 새로운 식 S(n)을 정의할 건데 그건 또 아래와 같다.

이럴 때 S(n)을 n에 관하여 정리해보자면 아래와 같이 정리된다.

이 때 다음을 구해서 출력하시오.

주어지는 것은 다음이다. 

문제 풀이 :

 사실 이런 종류의 수식을 처음 접하는 사람은 이게 대체 뭔 개소린가 싶은 느낌이 들 것이다. 정수론과 굉장히 밀접한 식인데 처음 읽었을 때 도무지 분석을 할 수가 없었다.

 S(n)을 f(k)로 풀어보자면 다음과 같다.

일단, 

이식을 보면 이걸 n에 관하여 정리해야 하는데, 정수론에 대해 기초 지식이 있는 사람들은 (사실 고딩때도 배운다) 거듭제곱의 합이 n에 관한 식으로 나온다는 사실을 알 수 있다. 

예를들면,

요런 것들? 

따라서 거듭제곱이 같은 것끼리 모아보자.

위 식을 정리하면 아래와 같이 깔끔하게 나오게 된다.

이제 필요한게 0<=t<=25 사이에 있는 모든 거듭제곱의 합의 계수들만 찾으면 답이다.

근데이게 쉽지가 않다. 이 걸 찾기 위해서는 가장 마지막에 주어진 식이 필요하다.

1부터 n까지 k제곱의 합을 앞으로 T(n,k)라 했을 때 다음과같다.

^증명보시려면 클릭하세요.

위 식을 정리하고나면 0~k-1의 거듭제곱합을 통해서 k거듭제곱합을 구할 수 있다.

따라서 0,1,2,3,4...25까지 미리 거듭제곱의 합을 구해놓고 처리하면 끝

소스코드 보기 <- 클릭

거듭 제곱의 합 

 우리가 고등학교 수열과정에 배우는 내용중 하나인 거듭제곱 공식에 대해서 배운다.

 사실 많은 사람들이 이 공식에 관해서 머리속에 박아 외우고 있는 사람들은 많지만 정작 이런 공식들이 어떻게 나오는 지에 관해서는 모르는 경우가 많다.

1~n까지 모든 자연수들의 합을 나타내면

다음과 같이 표기한다. 보통 시그마라고 읽는다.  보통 우리들은 이 공식들을 외우고 있다.

혹시 이 공식의 증명법을 모르시는 분들을 위해서 한번 정리해 보자면 1)식과 2)식을 더하면 3)식이 나오는데 이때 (n+1)의 갯수가 총 n개 존재한다.(1~n이 n개존재하므로) 따라서 n(n+1)이된다.

그리고 그식을 정리하면 마지막 공식이 톡하고 튀어나오게 되시겠다.

이런 것들을 정리해 보자면

그런데 이게 4일때는? 5일때는? 6일때는?... k일때는?.... 

넘나 복잡한 것

이제 우리가 하고자 하는 일은 아래의 식을 모든 정수 k에대해 n에 관한 식으로 나타내는 것이다.

사실 여기서부터가 재밌다. 어떤 점화관계가 주어지면 재귀적으로 쉽게 풀 수 있는 문제들이 있다. 이는 재귀적으로 정의하고 그것을 정리하면 n에관한 식을 손쉽게 표현하고 구할 수 있을 것이다. 

우리는 문제를 풀기 앞서서 아래의 공식을 배운 적 있을 것이다.

위와 같은 식이 성립함으로 인해서 우리는 이 식을 가지고 장난을 쳐 우리가 원하는 바를 이루어 낼 것이다. 

(이 식을 처음 보시는 분들은 이항 정리에 관하여 검색해 보세요)

우리가 원하는 바를 이루기 위해서는 k+1에 관한 식이 필요하다. 그 이유는 포스트를 쭉 읽다보면 이해 할 수 있을 것이다. (k를 k+1로 치환하도록 하자)

이제 이 식에서 

을 좌항으로 옮길 것이다. 그렇다면 아래와 같은 식이 나타난다.

그리고 우리는 이식을 보면 하고 싶은 짓이있을 것이다. 계차수열의 일반항을 구할 때 했던 방법. 이제부터 x에 1부터 n까지의 수를 대입해보도록 하자.

이제우리가 할일은? 

다 더하기

그러면 좌측항이 아주 이쁘게 정리되면서 아래와 같은 식을 얻을 수 있다.

우리가 구하고 싶은 것은 S(n,k)이므로 이것에 대해 정리하기 위해서 S(n,k)만 우항에 놔두고 모든 식을 좌항으로 옮기도록 하자. 그렇다면

짜란 이제 우리는 임의의 k가 주어졌을때 S(n,0)~S(n,k-1)을 사용해 k일때의 n에 관한 식으로 만들 수 있다.

즉 점화식을 완성한 것이다 ^ㅇ^

식을 정리해서 만들었으니 k=2일때 제대로 정리 되었는지 보자.

완젼 잘나오네요 ㅎㅎ

k=3일때랑 k=4일때도 해보세요. 저는 귀찮아서 하기싫어여…

사실 이 문제에 관해서 점화관계뿐만 아니라 일반항을 나타낼 수 있다. 베르누이 수를 이용해서라고... 

수학자가 아닌 내가 이해하기는 힘든 증명이라 링크만 달아 놓도록 하겠다. 

Faulhaber's formula

능력자 분들 중 이글을 보게 되는 분이 있다면 저것에 관해서 설명좀 부탁드려요..

이것과 관련된 알고리즘 문제 풀어보기

.

이걸 계산하는 프로그램을 원하시면 코멘트 달아주세요. 만들어 드리겠습니다.

참고

http://blog.naver.com/dalsapcho/20141141955