BOJ 21607 Polynomial and Easy Queries

문제 링크입니다.

식 정리하기

$f(x) = 2x^2-1, g(x) = 4x^3-3x$를 마구 합성해야 하는 문제입니다. 일단 $f(g(x))$와 $g(f(x))$를 각각 구해 봅시다.

• $f(g(x)) = 2(4x^3-3x)^2-1 = 32x^6 - 48x^4 + 18x^2-1$
• $g(f(x)) = 4(2x^2-1)^3-3(2x^2-1) = 32x^6 - 48x^4 + 18x^2-1$

위와 같이 식을 정리해 보면 $f(g(x)) = g(f(x))$가 성립합니다. 따라서, $f(g(f(f(g(g(f(x)\cdots)$와 같이 마구 섞여 합성된 함수를 합성의 순서를 적당히 바꿔서 $f(f(f(f(g(g(g(x)\cdots) = f^4g^3(x)$와 같이 표현할 수 있다는 겁니다.

합성한 값 전처리하기

이제 수열의 각 원소의 값을 그 위치에 $f$와 $g$가 각각 몇 번씩 씌워졌는지를 센 뒤에 그에 맞게 함수를 씌워주면 됩니다.

매번 함수를 씌워서 계산하기에는 시간이 오래 걸립니다. 모듈러가 $100\, 003$으로 그렇게 크지는 않음을 이용해, 각 값마다 각 함수를 몇 번 씌웠을 때 어떤 값으로 변하는 지를 전부 저장해 주는 방법을 떠올릴 수 있습니다.

근데 $100\,003$이 또 그렇게 작은 값도 아니라서… 그냥 구했다가는 쿼리가 들어올 때마다 계산하는 것만 못한 결과를 얻을 수 있습니다.

함수를 어떤 값이 들어오면 다른 값으로 보내는 간선의 집합이라고 생각한다면, 1번 정점에서 출발해 간선을 4번 타면 보내지는 정점 = 1번 정점에서 출발해 간선을 2번 타서 보내지는 정점에서, 다시 간선을 2번 타서 보내지는 정점 = $f^4(1)$ = $f^2(f^2(1))$과 같이 생각할 수 있습니다.

요컨대, $f, f^2, f^4, …$와 같이 2의 거듭제곱 번 합성한 함수에 대한 결괏값만 있어도 모든 합성함수에 대한 각 출발점에서의 도착점을 알아낼 수 있습니다. 희소 배열이라 불리는 이 방법을 이용해 우리가 실제로 저장해 두어야 하는 값을 $100\,003\,Q$개에서 $100\,003\, \log Q$ 개로 줄일 수 있습니다.

합성한 횟수 세기

구간 업데이트 / 점 쿼리가 들어옵니다. 세그먼트 트리나 펜윅 트리를 이용해 업데이트가 들어올 때마다 카운트를 올려주면 각 원소마다 두 함수가 얼마나 들어갔는지는 쉽게 알 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
constexpr int mod = 100003;

int f[30][mod], g[30][mod];

int a[505050];
int ffen[505050], gfen[505050];

void upd(int fen[], int i, int v){
	for(;i<=500500;i+=i&-i) fen[i] += v;
}

int qry(int fen[], int i){
	int ret = 0;
	for(;i;i-=i&-i) ret += fen[i];
	return ret;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	for(ll i = 0; i < mod; i++) f[0][i] = (2*i*i-1)%mod;
	for(int bit = 1; bit < 30; bit++) for(int i = 0; i < mod; i++) f[bit][i] = f[bit-1][f[bit-1][i]];
	for(ll i = 0; i < mod; i++) g[0][i] = (4*i*i*i-3*i)%mod;
	for(int bit = 1; bit < 30; bit++) for(int i = 0; i < mod; i++) g[bit][i] = g[bit-1][g[bit-1][i]];
	
	int n, Q; cin >> n >> Q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	while(Q--){
		int q; cin >> q;
		if(q == 1){
			int l, r; cin >> l >> r;
			upd(ffen, l, 1);
			upd(ffen, r+1, -1);
		}
		if(q == 2){
			int l, r; cin >> l >> r;
			upd(gfen, l, 1);
			upd(gfen, r+1, -1);
		}
		if(q == 3){
			int x; cin >> x;
			int ans = a[x];
			int F = qry(ffen, x), G = qry(gfen, x);
			for(int bit = 0; bit < 30; bit++){
				if(F & (1<<bit)) ans = f[bit][ans];
				if(G & (1<<bit)) ans = g[bit][ans];
			}
			cout << ans << '\n';
		}
	}	
}