백준 1492번: 합

www.acmicpc.net/problem/1492

1492번: 합

---

처음 봤을 때 굉장히 당황했던 문제입니다. 그리고 개인적으로 꽤나 피곤한 문제였습니다.

 

$K$의 범위가 상당히 작긴 하지만, $N$개의 항을 모두 구해서 더하는 건 말도 안 되는 짓이라는 걸 바로 알 수 있습니다.

 

그렇다면 뭔가 방법이 있다는 뜻입니다.

 

이제 $1^{K}+2^{K}+3^{K}+\cdots+N^{K}=Sum\left ( N,K \right )$ 라고 해보겠습니다.

 

그렇다면 $Sum\left ( N,K \right )$와 $Sum\left ( N+1,K \right )$에 어떤 관계가 있는 걸까요?

 

우선 이걸 알 수 있습니다.

 

$\left ( N+1 \right )^{K}=Sum\left ( N+1,K \right )-Sum\left ( N,K \right )$

 

그런데,

 

$Sum\left ( N+1,K \right )=\left ( N+1 \right )^{K}+N^{K}+\cdots+2^{K}+1^{K}$

$Sum\left ( N,K \right )=N^{K}+\left ( N-1 \right )^{K}+\cdots+1^{K}$

 

이므로 이를 다음과 같이 묶을 수 있습니다.

 

$Sum\left ( N+1,K \right )-Sum\left ( N,K \right )$

 

$=\left ( \left ( N+1 \right )^{K}-N^{K} \right )+\left ( N^{K}-\left ( N-1 \right )^{K} \right )+\cdots+\left ( 2^{K}-1^{K} \right )+1^{K}$

 

따라서 시그마를 사용하면 다음과 같은 식을 얻을 수 있습니다.

 

$\left ( N+1 \right )^{K}-1^{K}=\sum_{m=1}^{N}\left ( \left ( m+1 \right )^{K}-m^{K} \right )$

 

여기서 한 단계 더 나아가서,

 

이항계수 $\large \binom{n}{r}$을 도입하면 다음을 알 수 있습니다.

 

$\left ( m+1 \right )^{K}-m^{K}=\sum_{i=0}^{K-1}\binom{K}{i} m^{i}$

 

이를 이용하여 식을 변형하면

 

 $\sum_{m=1}^{n}\left ( \left ( m+1 \right )^{K}-m^{K} \right )$

 

 $=\sum_{m=1}^{N}\sum_{i=0}^{K-1}\binom{K}{i} m^{i}$

 

$=\sum_{i=0}^{K-1}\binom{K}{i}\times \sum_{m=1}^{N}m^{i}$

 

$=\sum_{i=0}^{K-1}\left ( \binom{K}{i} \times Sum\left ( N,i \right ) \right )$

 

을 얻을 수 있습니다.

 

결과적으로

 

$\left ( N+1 \right )^{K}-1^{K}=\sum_{i=0}^{K-1}\left ( \binom{K}{i} \times Sum\left ( N,i \right ) \right )$

 

이므로 다음을 얻을 수 있습니다.

 

$Sum\left ( N,K-1 \right )\times \binom{K}{K-1}=\left \{ \left ( N+1 \right )^{K}-1^{K} \right \}-\sum_{i=0}^{K-2}\left (\binom{K}{i} \times Sum\left ( N,i \right ) \right )$

 

이제 식을 좀 더 보기 좋게 하기 위해

 

$K$의 자리에 $K+1$을 대입해보면 다음과 같습니다.

 

$Sum\left ( N,K \right )\times \binom{K+1}{K}=\left \{ \left ( N+1 \right )^{K+1}-1^{K+1} \right \}-\sum_{i=0}^{K-1}\left (\binom{K+1}{i} \times Sum\left ( N,i \right ) \right )$

 

이때 $K$의 값이 50 이하로 매우 작기 때문에, $Sum\left ( N,K \right )$을 메모이제이션을 통해 구할 수 있게 되었습니다.

 

이항계수 $\binom{K+1}{0}$ ~ $\binom{K+1}{K-1}$은 파스칼의 삼각형으로 구하면 충분함을 알 수 있습니다.

 

파스칼의 삼각형으로 이항계수를 구하면 $O\left ( N^{2} \right )$이지만, $K\leq 50$이므로 시간 안에 들어오기 때문입니다.

 

문제에서는 오버플로우를 방지하기 위해 $Sum\left ( N,K \right )$의 modulo $\left ( 10^{9}+7 \right )$ 값을 구하라고 하고 있는데,

 

좌변의 $\binom{K+1}{K}$가 걸립니다.

 

모듈러 상에서의 나눗셈을 역원을 곱하는 걸로 바꿔서 생각하면, $\binom{K+1}{K}$의 모듈러 곱셈 역원을 구해야 하는데

 

다행히 이는 페르마의 소정리를 활용해 쉽게 해결할 수 있습니다.

 

최종적으로, $Sum\left ( N,0 \right )=N$인 것과 다음 식을 이용해 차근차근 구하면 되는 문제였습니다.

 

 $ \binom{K+1}{K} ^{-1} \times \left [ \left \{ \left ( N+1 \right )^{K+1}-1 \right \}-\sum_{p=0}^{K-1}\left ( \binom{K+1}{p}\times Sum \left ( N,p \right ) \right ) \right ]=Sum\left ( N,K \right ) \left ( mod \left ( 10^{9}+7 \right ) \right )$

 

코드는 다음과 같습니다.

 

#include <stdio.h>
#define mod 1000000007

long long array_nCk_modulo[52][52]; 
long long array_sum_of_powers[51];

long long multiply_modular (long long x, long long y); // (x * y) mod M
long long power_modular    (long long x, long long y); // (x ^ y) mod M

int main() {
	//preprocessing nCk
	long long i, j;
	for (i = 0; i <= 51; i++) {
		array_nCk_modulo[i][0] = array_nCk_modulo[i][i] = 1;
		for (j = 1; j < i; j++) {
			array_nCk_modulo[i][j] = (array_nCk_modulo[i-1][j] + array_nCk_modulo[i-1][j-1]) % mod;
		}
	}
	//
	long long N, K;
	scanf("%lld %lld", &N, &K);
	//
	array_sum_of_powers[0] = N; // 1^0 + 2^0 + ... + N^0 = N
	//faulhaber's formula
	for (i = 1; i <= K; i++) {
		
		long long temp = power_modular(N+1, i+1) - 1;
		
		for (j = 0; j <= i - 1; j++) {
			temp -= multiply_modular(array_nCk_modulo[i+1][j], array_sum_of_powers[j]);
			if (temp < 0) {
				temp = (temp + mod) % mod;
			}
			else {
				temp %= mod;
			}
		}
		
		temp = multiply_modular(temp, power_modular(array_nCk_modulo[i+1][i] , mod - 2));
		
		array_sum_of_powers[i] = temp;
	}
	//
	printf("%lld", array_sum_of_powers[K]);
	//
	return 0;
}

long long multiply_modular (long long x, long long y) {
	x %= mod;
	y %= mod;
	long long result = 0;
	while (y > 0) {
		if (y & 1) {
			result = (result + x) % mod;
		}
		x = (x + x) % mod;
		y >>= 1;
	}
	return result;
}

long long power_modular (long long x, long long y) {
	x %= mod;
	long long result = 1;
	while(y > 0) {
		if (y & 1) {
			result = (result * x) % mod;
		}
		x = (x * x) % mod;
		y >>= 1;
	}
	return result;
}

 

(C11, 1136KB, 0ms, 제출번호 26522409)

---

사실 제가 유도한 식은 위키피디아에서 faulhaber's formula 문서를 찾아보면 나오는 식입니다.

 

하지만 유도과정이 안 적혀있기도 하고, 애초에 faulhaber's formula라는 게 존재하는 지도 모르는 사람이 더 많을 것 같습니다...

 

만약 $Sum\left ( N,K \right )$와 $Sum\left ( N,K+1 \right )$ 사이의 어떤 관계식이 있었다면 식이 좀 더 쉬워졌을까요?

 

그것과는 별개로 본문의 방법을 이용해서 빠르게 구할 수 있는 $Sum\left ( N,K \right )$의 범위가 궁금하네요.

 

$\binom{1000}{1000}$까지 구하는 문제가(11051번, 이항계수2) 파스칼의 삼각형을 써서 대략 4ms정도 걸렸었는데

 

그걸 생각해보면 $K$가 1000까지 높아져도 괜찮을 것 같기도 합니다.

 

파스칼의 삼각형을 버린다고 하면 $K$를 1만 근처?까지 높일 수도 있겠습니다.

 

코드를 쭉 짜다가 알게 됐는데, 이항계수가 주어진다고 해도

 

제 코드의 시간 복잡도가 $O\left ( K^{2} \right )$쯤 되니 $K$를 무식하게 크게는 못 키우겠다 싶네요.