취미로 코딩하기

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

이번에 볼 문제는 백준 32065번 문제인 Short Function이다.
문제는 아래 링크를 확인하자.

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

주어진 식이 값을 곱해나가는 규칙이 마치 sparse table(희소 테이블)의 값을 채워나가는 과정과 유사해보이지 않는가?

위 관찰을 이용하면, 각 A[i]의 값은 결국 주어진 배열이 끝없이 반복되는 수열의 i번째 항부터 시작되는 길이 $2^K$의 배열에 적힌 수의 곱이 됨을 알 수 있다. 대충 $2^K$을 $N$으로 나눈 몫만큼 배열 전체의 곱을 곱하고, 나머지만큼 배열의 구간곱을 구해 둘을 곱하는 것으로 원하는 값을 계산하자.

그런데 이 값을 그냥 계산하기에는 $2^K$의 값이 너무 커서 계산이 어렵다. 구하고자 하는 값이 소수 998244353으로 나눈 나머지이므로, 배열 전체를 998244352회 곱한 값이 1이 됨을 이용해 이 과정을 가능하게 만들자. 즉, $2^K$을 $N$으로 나눈 몫 대신 이 값을 998244352로 나눈 나머지를 이용해도 문제의 답이 같게 나옴을 이용하자. 이는 998244353이 소수이고 배열을 구성하는 각 원소가 998244353의 배수가 아니므로 가능하다.

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

#include <iostream>
using namespace std;
typedef __int128 lll;

int tmp;
lll MOD = 998244353, NMOD, ansconst, qrylen;
lll N, K, total = 1, A[100001];
lll totalcnt;

lll seg[262145];
lll init(int L, int R, int sI) {
	if (L < R) return seg[sI] = init(L, (L + R) / 2, sI * 2) * init((L + R) / 2 + 1, R, sI * 2 + 1) % MOD;
	return seg[sI] = A[L];
}
lll qry(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 1;
	if (qL <= L && R <= qR) return seg[sI];
	return qry(L, (L + R) / 2, qL, qR, sI * 2) * qry((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1) % MOD;
}

lll bexp(lll X, lll KK) {
	lll ret = 1;
	while (KK) {
		if (KK & 1) ret = ret * X % MOD;
		KK >>= 1, X = X * X % MOD;
	}
	return ret;
}

lll func(lll x, lll M) { // 2^x의 mod M을 계산
	lll ret = 1, val = 2;
	while (x) {
		if (x & 1) ret = ret * val % M;
		val = val * val % M;
		x >>= 1;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> tmp; N = tmp;
	cin >> tmp; K = tmp;
	NMOD = N * (MOD - 1);
	for (int i = 1; i <= N; i++) {
		cin >> tmp, A[i] = tmp;
		total = total * A[i] % MOD;
	}
	totalcnt = func(K, NMOD) / N;
	ansconst = bexp(total, totalcnt);
	qrylen = func(K, N);

	if (!qrylen) {
		for (int i = 1; i <= N; i++) cout << (int)ansconst << ' ';
		return 0;
	}
	
	init(1, N, 1);
	for (int i = 1; i <= N; i++) {
		int L = i, R = i + qrylen - 1;
		if (R <= N) cout << (int)(ansconst * qry(1, N, L, R, 1) % MOD) << ' ';
		else cout << (int)(ansconst * (qry(1, N, L, N, 1) * qry(1, N, 1, R - N, 1) % MOD) % MOD) << ' ';
	}
}

랜덤 마라톤 · 코스 12 H번