[BOJ 6150 // C++] Summing Sums

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6150번 문제인 Summing Sums이다.
문제는 아래 링크를 확인하자.

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

6150번: Summing Sums

맨 처음에 소들이 결정한 숫자들이 T단계 후의 수에 몇 개씩 들어가게 되는지 관찰하는 것으로 문제를 해결할 수 있다.

 

T의 값이 크므로, 선형결합의 성질과 binary exponentiation을 이용하여 계산과정의 시간복잡도를 줄이자.

 

또한, N=1인 경우의 예외처리를 잊지 말자. (T>0이므로 항상 0 하나를 출력하게 구현하는 것으로 충분하다)

 

아래는 제출한 소스코드이다.

#define MOD 98765431
#include <iostream>
using namespace std;
typedef long long ll;

ll arr[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	ll total = 0;
	ll N, T; cin >> N >> T;
	for (int i = 0; i < N; i++) {
		ll x; cin >> x;
		arr[i] = x;
		total += x;
	}
	total %= MOD;

	if (N == 1) {
		cout << 0;
		return 0;
	}

	bool odd = 0;
	if (T & 1) odd = 1;
	ll a = 1, b = 0, p = ((N - 1) * (N - 1)) % MOD, q = N - 2;
	T >>= 1;
	while (T > 0) {
		if (T & 1) {
			ll tempa = (a * p) % MOD;
			ll tempb = (a * q + b) % MOD;
			a = tempa, b = tempb;
		}
		ll tempp = (p * p) % MOD;
		ll tempq = (p * q + q) % MOD;
		p = tempp, q = tempq;
		T >>= 1;
	}
	if (odd) {
		ll tempa = (a * (N - 1)) % MOD;
		ll tempb = (b * (N - 1) + 1) % MOD;
		a = tempa, b = tempb;
	}

	total = (total * b) % MOD;
	if (odd) {
		for (int i = 0; i < N; i++) {
			ll ans = total - arr[i];
			if (ans < 0) ans += MOD;
			cout << ans << '\n';
		}
	}
	else {
		for (int i = 0; i < N; i++) {
			ll ans = (total + arr[i]) % MOD;
			cout << ans << '\n';
		}
	}
}