公式

D - Popcount and XOR 解説 by en_translator


Let \(n _ {i,j}\) be the number of \(k\)’s such that the \(k\)-th digit of the binary representation of \(X\) and \(Y\) are \(i\) and \(j\ (i,j\in\lbrace0,1\rbrace)\), respectively.

According to the given conditions, we have the following:

  • \(\operatorname{popcount}(X)=a\iff n _ {1,0}+n _ {1,1}=a\)
  • \(\operatorname{popcount}(Y)=b\iff n _ {0,1}+n _ {1,1}=b\)
  • \(X\oplus Y=C\implies n _ {1,0}+n _ {0,1}=\operatorname{popcount}( C)\)

Let \(c\coloneqq\operatorname{popcount}( C)\).

Since \(n _ {0,0}+n _ {0,1}+n _ {1,0}+n _ {1,1}=60\), the values \(n _ {i,j}\) must satisfy the following:

\[\begin{aligned} n _ {0,0}&=60-\dfrac{a+b+c}2\\ n _ {0,1}&=\dfrac{-a+b+c}2\\ n _ {1,0}&=\dfrac{a-b+c}2\\ n _ {1,1}&=\dfrac{a+b-c}2 \end{aligned}\]

Since they have to be non-negative integers, if any of the following condition is met, there is no conforming \((X,Y)\):

  • \(a+b+c\equiv1\pmod2\)
  • \(a+b+c\gt120\)
  • \(a\gt b+c,b\gt c+a,c\gt a+b\).

If none of the above is satisfied, \(n _ {i,j}\) are non-negative integers. In such case, \((X,Y)\) can be actually constructed as follows:

Let \(S _ 0\) be the sequence consisting of \(n _ {0,0}\) copies of \((0,0)\) and \(n _ {1,1}\) copies of \((1,1)\), and \(S _ 1\) be the sequence consisting of \(n _ {0,1}\) copies of \((0,1)\) and \(n _ {1,0}\) copies of \((1,0)\).
For \(k=0,1,2,\ldots,59\), perform the following:

  • Let \(b\) be the \(2^k\)s place of \(C\). Retrieve and remove the last element of \(S _ b\). Let \((x,y)\) be the retrieved element, and set the \(2 ^ k\)s place of \(X\) and \(Y\) to \(x\) and \(y\), respectively.

Sample code is shown below. In this sample code, instead of explicitly maintaining \(S _ 0\) and \(S _ 1\), only the remaining number of \((0,0),(0,1),(1,0)\), and \((1,1)\) are managed. Also, by determining the most significant bits first, we simplify the process of obtaining the integers from the digits in its binary representation.

#include <iostream>
#include <bit>

int main() {
    using namespace std;
    unsigned a, b;
    unsigned long C;
    cin >> a >> b >> C;
    unsigned c = popcount(C);

    if((a + b + c) % 2 != 0 || a + b + c > 120 || a > b + c || b > c + a || c > a + b){
        cout << "-1" << endl;
        return 0;
    }

    // n?? = the number of k such that the k-th digit of X and Y are ??
    unsigned n00{60 - (a + b + c) / 2}, n01{(-a + b + c) / 2}, n10{(a - b + c) / 2}, n11{(a + b - c) / 2};

    unsigned long X{}, Y{};
    for(unsigned B = 60; B--;){ // Scan from the higher digit
        // Lift one bit each
        X *= 2;
        Y *= 2;

        if(1 & (C >> B)){ // If B-th bit of C is 1
            if(n10){ // if (1, 0) is in stock
                ++X; // set the B-th bit of X to 1, and of Y to 0
                --n10; // consume the stock
            }else{ // otherwise
                ++Y; // set that of Y to 1
                --n01; // consume the stock
            }
        }else{ // If B-th bit of C is 0
            if(n00){ // if (0, 0) is in stock
                --n00; // set both of them to 0, and consume the stock
            }else{ // otherwise
                ++X; // set both of them to 1,
                ++Y;
                --n11; // and consume the stock
            }
        }
    }

    cout << X << " " << Y << endl;
    return 0;
}

投稿日時:
最終更新: