Boj 25563) And, Or, Xor

문제

백준 25563

설명

Sum of Subsets DP(SOS DP) 문제이다.

XOR 은 어떤 수가 있다면 Xor 연산으로 K 를 만드는 수는 정해져 있어서 간단하다.

And 와 Or 은 SOS DP 를 이용해 풀면 된다.

• 이때 Or 를 처리할 때 SOS 의 특성 상 포함배제의 원리로 풀기가 어렵다. 잘 알려진 SOS 로직과 방향을 거꾸로 하면 간단히 구할 수 있다.

시간 복잡도

O(\(\mathrm{N} \log{\mathrm{N}}\))

코드

using ll = unsigned long long;
const ll MAX_IN = 1 << 20;
ll n, k, arr[MAX_IN], dp[MAX_IN];

void Solve()
{
	ll r1 = 0, r2 = 0, r3 = 0;

	// and.
	fill(dp, dp + MAX_IN, 0);
	for (int i = 0; i < n; i++)
		if ((k & arr[i]) == k)
			dp[arr[i]]++;

	for (int i = 1; i < MAX_IN; i <<= 1)
		for (int x = 0; x < MAX_IN; x++)
			if (i & x)
				dp[x] += dp[x ^ i];

	for (int i = 0; i < n; i++)
	{
		if ((k & arr[i]) != k) continue;
		r1 += dp[(MAX_IN - 1) & (k | ~arr[i])];
		r1 -= arr[i] == k; // 자기자신인 경우 중복
	}
	r1 >>= 1; // 중복 제거

	// or
	fill(dp, dp + MAX_IN, 0);
	for (int i = 0; i < n; i++)
		if ((arr[i] & ~k) == 0)
			dp[arr[i]]++;

	for (int i = 1; i < MAX_IN; i <<= 1)
		for (int x = MAX_IN - 1; x >= 0; x--)
			if (i & x)
				dp[x ^ i] += dp[x];

	for (int i = 0; i < n; i++)
	{
		if (arr[i] & ~k) continue;
		r2 += dp[k & ~arr[i]];
		if (k == arr[i]) r2--;
	}
	r2 >>= 1;

	// xor.
	fill(dp, dp + MAX_IN, 0);
	for (int i = 0; i < n; i++)
		dp[arr[i]]++;

	for (int i = 0; i < n; i++)
	{
		auto t = (arr[i] & ~k) | (k & ~(arr[i] & k));
		r3 += dp[t];
		if (t == arr[i]) r3--;
	}
	r3 >>= 1;

	cout << r1 << ' ' << r2 << ' ' << r3;
}

int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> arr[i];
	Solve();
}