BOJ 28142 연산자 파티 2

문제 링크입니다.

나이브한 처리

$-i$ , $\times i$, $\land i$, $\oplus i$, $\vee i$, $\ll i$ 연산을 각각 i가 1의 배수, 3의 배수, 15의 배수, 63의 배수, 255의 배수, 1023의 배수가 되었을 때마다 쓰여진 순서대로 실행하면 됩니다. 총 시간복잡도는 $\mathcal{O}(N)$으로 나쁘지 않지만, 아쉽게도 이 문제는 이보다 빠른 시간 복잡도를 요구합니다.

연산 합성하기

i의 값에 따라 여러 개의 연산이 연속해서 실행되는 경우가 있습니다. 예를 들어, 매 3의 배수마다 $X = \vert X-i \vert \times i$ 가 실행됩니다.

그중 $\land$ 연산과 $\lor$ 연산에 집중합시다. 임의의 $X$, $i$에 대해, $(X \land i)$ 에서의 켜진 비트는 반드시 $i$에서의 켜진 비트의 일부입니다. 또 $(X \lor i)$의 켜진 비트는 $i$에서의 켜진 비트와 $X$에서의 켜진 비트의 합집합입니다.

그러면 $(X \land i) \lor i$ 는 ($i$에서의 켜진 비트 중 일부만 켜진 것) 과 ($i$에서의 켜진 비트)의 합집합에 해당하는 비트가 켜진 상태인 수가 됩니다. 즉 모든 $X$, $i$에 대해 $(X \land i) \lor i = i$가 성립합니다.

같은 논리로 $X \land i \oplus i \lor i = i$ 또한 성립함을 보일 수 있습니다.

계산 횟수 줄이기

$\land$와 $\lor$는 $i$가 255의 배수일 때마다 함께 등장합니다. 그 말인즉슨, 255의 배수가 될 때마다 이전의 연산이 뭐가 어떻게 돌아갔든 간에 $\lor$ 연산을 처리한 뒤에는 $X = i$가 된다는 뜻입니다.

그러니 $i$를 1부터 시작하지 말고, $N$ 이하의 가장 큰 255의 배수부터 시작해도 같은 결괏값을 얻을 수 있습니다.

« 연산 처리하기

직접 비트를 밀거나 하기에는 $i$의 값이 많이 큽니다. 2의 $i$제곱을 $X$에 곱하는 방식으로 처리해 줍시다. 분할 정복을 이용한 거듭제곱으로 가능합니다.

최종적으로 거의 상수 수준의 시간에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
ll pw(ll n){
	ll ret=1,a=2;
	while(n){
		if(n&1)ret=ret*a%mod;
		a=a*a%mod;
		n>>=1;
	} return ret;
}
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	ll x = 0, n, l; cin >> n;
	l = n-n%255;
	for(ll i = l; i <= n; i++){
		x -= i; if(x < 0) x = -x;
		if(i%3 == 0) x = (x%mod)*(i%mod)%mod;
		if(i%15 == 0) x &= i;
		if(i%63 == 0) x ^= i;
		if(i%255 == 0) x |= i;
		if(i%1023 == 0) x = x%mod*pw(i)%mod;
	} cout << x;
}