BOJ 15679 수열의 개수

문제 링크입니다.

문제 요약

각 원소가 31비트 정수로 표현되는 길이 $N$의 수열들 중 정확히 $C$개가 다음의 세 조건을 만족하도록 하는 세 정수 $X, Y, Z$의 조합을 하나 찾으세요.

• 수열의 모든 원소를 bitwise OR한 결과가 $X$
• 수열의 모든 원소를 bitwise AND한 결과가 $Y$
• 수열의 모든 원소를 bitwise XOR한 결과가 $Z$

풀이

문제를 비트 별로 분리해서 생각할 수 있습니다. 수열의 각 원소가 0 또는 1이고, $X,Y,Z$ 또한 0 또는 1이라고 생각하면 총 8가지 조합이 있음을 확인할 수 있습니다. $(X,Y,Z)$에 따라 이를 구분해 보면,

• $(0,0,0)$ : 모든 원소가 0입니다. 1가지 수열이 이를 만족합니다.
• $(0, 0, 1), (0,1,0),(0,1,1)$: $X = 0$ 이려면 모든 원소가 0이여야 하므로 불가능합니다.
• $(1,1,1) / (1,1,0)$ : 모든 원소가 1이여야 합니다. $N$의 홀짝성에 따라 하나는 만족하는 수열이 1가지 존재하고 다른 하나는 불가능합니다.
• $(1,0,1)/(1,0,0)$ : 이 경우가 수열의 개수를 늘리는 데 핵심적인 역할을 합니다. 원소들이 모두 1도, 모두 0도 아니면서 1의 개수가 홀수/짝수인 경우의 수가 각각의 조합에 배정됩니다. $N$의 홀짝성에 따라 이는 $2^{N-1} -0 \sim 2$ 사이의 값이 됩니다. 이렇게 나뉘는 이유는 이항정리로부터 확인할 수 있습니다.

우리에게는 31개의 비트가 주어졌고, 수열의 개수는 $(1,0,1)$과 $(1,0,0)$의 개수로만 결정됩니다. 나머지는 $(0,0,0)$으로 채워주면서 가능한 모든 경우를 시도해 보면, 실제로 유효한 경우의 수는 $31^2$가지 이하이므로 문제를 해결할 수 있습니다.

코드

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

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	ll n, c; cin >> n >> c;
	if(!c) return !(cout << "0 0 1");
	if(c == 1) return !(cout << "0 0 0");
	int lgc = 0; ll cc = c+2; while(cc){
		cc >>= 1; lgc++;
	}
	if(n-2 > lgc) return !(cout << -1);
	for(int i = 0; i <= 31; i++) for(int j = 0; i+j <= 31; j++){
		__int128 t = 1;
		bool flag = 1;
		for(int ii = 0; ii < i; ii++){
			t *= (1LL<<n-1)-2+(n&1);
			if(t > c){
				flag = 0;
				break;
			}
		}
		for(int jj = 0; jj < j; jj++){
			t *= (1LL<<n-1)-(n&1);
			if(t > c){
				flag = 0;
				break;
			}
		}
		if(!flag) continue;
		if((ll)t == c){
			ll X = 0, Y = 0, Z = 0;
			for(int ii = 0; ii < i+j; ii++) X |= (1LL<<ii);
			for(int jj = 0; jj < j; jj++) Z |= (1LL<<jj);
			cout << X << ' ' << Y << ' ' << Z << '\n';
			return 0;
		}
	}
	cout << -1;
}