题解：AT_abc347_d [ABC347D] Popcount and XOR

_Trangle_ · 2024-04-06 11:58:41 · 题解

solution

显然，当 C 的某位取值为 1 时，a 和 b 的这一位的值相异。

所以它们二进制下 1 的个数的差就是从这里来的。

根据和差问题的解决方法，所以 X 和 C 同取值为 1 的位数为 \dfrac{a-b+\operatorname{popcount(C)}}{2}，而 X 和 Y 不与 C 同取值为 1 的位数是 a 减去 X 和 C 同取值为 1 的位数。

根据上面的方法模拟，最后判断是否合法即可。

code

#include <bits/stdc++.h>
#define rep(i, b, e) for (auto i(b); i != (e); i++)
#define req(i, b, e) for (auto i(b); i >= (e); i--)
using namespace std;

int a, b, p, must1a, need1a;
long long X, Y, C;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> a >> b >> C;
    p = __builtin_popcountll(C);
    must1a = a - b + p >> 1;
    need1a = a - must1a;

    for (long long i = 1; i <= 1ll<<60; i <<= 1) {
        if (C & i) {
            if (must1a) {
                must1a--;
                X |= i;
            }
            else Y |= i; //如果 X 和 C 同取 1 的位数达到要求，那么 Y 要和 C 同取 1
        }
        else if (need1a) {
            need1a--;
            X |= i; Y |= i;
        }
    }

    if (__builtin_popcountll(X) == a && __builtin_popcountll(Y) == b && X ^ Y == C) cout << X << ' ' << Y;
    else cout << -1;

    return 0;
}