백준 25974: 거듭제곱의 합 1

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

25974번: 거듭제곱의 합 1

 

---

 

[BOJ1492]에서 지수 크기의 상한을 1000으로 높인 버전입니다. 따라서 풀이는 백준 1492번: 합 과 같습니다.

 

다음은 제 코드입니다.

#include <stdio.h>
#define mod 1000000007

long long array_nCk_modulo[1002][1002]; // array of          (nCk)          mod (10^9 + 7), 0 <= k,n  <= 1001
long long array_sum_of_powers[1001]; // array  of (1^K + 2^K + ... + N^K) mod (10^9 + 7), 0 <=  K   <= 1000

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

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

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

(C11, 8968KB, 8ms, 제출번호 53638965)

---

 

위에서 제가 언급했던 제 블로그의 1492번 포스팅에서, 지수 상한을 1000으로 늘릴 수 있을 것 같다고 했는데 정말 그런 문제가 나와서 깜짝 놀랐습니다. 막상 1000까지 늘려도 8ms인 걸 보면, mod가 작으니까 이항계수 배열을 int 배열로 선언하고 상한을 늘릴 수 있을 것 같습니다. 25974번의 512MB, 1s 제한을 지키려면 대략 10000이 상한일 것 같습니다만...