[Python] 백준 1492 - 합, 백준 25974 - 거듭제곱의 합 1

https://www.acmicpc.net/problem/1492

https://www.acmicpc.net/problem/25974

풀이

수학 심층을 열심히 대비하고있는데, 분명 어디선가 본 것같기도 하고 아닌 것 같기도 한 점화식.

아마 운 좋으면 대입에도 나올 수도....?

 

한 번 유도해보자.

우리가 원하는 값을 $S_k$라고 정의하자.

 

누구나 알고있는 이항계수 전개식

 

우리는 위와 같은 이항계수 전개식을 생각해줄 수 있을 것이다. 심심하니까 x 대신 N을 넣어보자.

 

 

우리는 1부터 N까지의 거듭제곱들을 원하기 때문에, 거듭제곱의 밑을 바꿔주어야겠다는 생각을 할 수 있다.

이제 1+N 대신 N, N-1, N-2 .... 3, 2를 대입하고 쭉 적어보자.

 

 

맨 마지막 끝부분이 kCk인데, 이는 1과 같다. 그러니까 다음과 같이 전부 더해주면 축차?가 어느정도 가능하다.

 

 

그러면 식을 좀 정리하면 다음과 같은 관계식을 얻을 수 있다.

 

 

K를 1씩 올려주고 이항하면 다음과 같은 관계식을 얻을 수 있다.

 

 

이 공식을 약간 일반화한 것을 파울하버의 공식이라고 부르는 모양이다.

 

이를 파이썬으로 구현하는 것은 쉽다. math 라이브러리의 comb 함수를 쓰면 바로 이항계수 계산이 가능하다.

다만 많은 사람들이 하는 실수중에, 나누기 연산은 MOD 연산이 잘 적용되지 않는다.

따라서 페르마 소정리를 이용해서 모듈러 역원을 구해준 다음 이를 곱해주어야 한다.

 

코드는 아래와 같다.

 

from math import comb
MOD = 1_000_000_007
N, K = map(int, input().split())
dp = [0]*(K+1)
dp[0] = N
for i in range(1, K+1):
    tmp = pow(N+1, i+1, MOD) - 1
    for j in range(i):
        tmp -= dp[j]*comb(i+1, j)
        tmp %= MOD
    dp[i] = (tmp*pow(comb(i+1, i), MOD-2, MOD))%MOD
print(dp[-1])

 

 

 

참고로, 25974의 경우 k가 1000까지 커졌기 때문에 math 의 comb을 바로 쓰다가는 TLE 받을 수도 있다. 그래서 다음과 같이 미리 팩토리얼을 계산해놓고 직접 comb 함수를 구현해야 한다.

 

MOD = 1_000_000_007
N, K = map(int, input().split())
dp = [0]*(K+1)
dp[0] = N
fac = [1]
for i in range(1, K+2):
    fac.append(fac[i-1]*i%MOD)
def comb(n, k):
    a = pow(fac[k], MOD - 2, MOD)
    b = pow(fac[n-k], MOD - 2, MOD)
    return fac[n] * a * b % MOD
for i in range(1, K+1):
    tmp = pow(N+1, i+1, MOD) - 1
    for j in range(i):
        tmp -= dp[j]*comb(i+1, j)
        tmp %= MOD
    dp[i] = (tmp*pow(comb(i+1, i), MOD-2, MOD))%MOD
print(dp[-1])