Asia Regional - Daejeon 2015 H. Polynomial 솔루션

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까지 미리 거듭제곱의 합을 구해놓고 처리하면 끝

 

소스코드 보기 <- 클릭