백준 14731번: 謎紛芥索紀 (Large)

www.acmicpc.net/problem/14731

14731번: 謎紛芥索紀 (Large)

---

사진에서 세번째 줄에서 따온 문제입니다.

 

힌트에서 혹시 다항함수를 어떻게 미분할 지 모르는 경우를 위해 다항함수를 미분하는 예시를 보여줬습니다.

 

참고로 small 문제는 (www.acmicpc.net/problem/14730) 좀 더 간편하게 미분 된 함수의 계수의 합만 구하는 걸로 출제되었습니다.

 

이 Large문제는 $N$개의 $K$, $C$를 입력받을 때 $C\times K\times 2^{K-1}$의 합을 구해주면 해결됩니다.

 

$C$가 양수로 제한되어 모듈로 연산을 수행할 때 주의해야할 점이 딱히 없습니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>
#define modulo 1000000007

long long power_modular (long long x, long long y, long long M);

int main() {
	int N;
	scanf("%d", &N);
	long long sum = 0;
	long long C, K;
	int i;
	for (i = 0; i < N; i++) {
		scanf("%lld %lld", &C, &K);
		long long temp;
		if (K >= 1) {
			temp = (((C * K) % modulo) * power_modular(2, K-1, modulo)) % modulo;
		}
		else {
			temp = 0;
		}
		sum = (sum + temp) % modulo;
	}
	printf("%lld", sum);
	return 0;
}

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

 

(C11, 1116KB, 44ms, 제출번호 25936705)

---

정수 $x$를 추가적으로 입력받아 $f'\left(x \right )$를 구하도록 만들 수도 있는 문제인데 그 점은 살짝 아쉬운 것 같습니다.