Problem Statement

Given are integers \(M\), \(N\), and \(V\). Find the number of pairs of integers \((l, r)\) that satisfies all of the conditions below, modulo \(998244353\).

• \(0 \le l \le M\)

• \(0 \le r \le N\)

• \(l \xor r = V\)

Here, \(\xor\) denotes the bitwise XOR operation.

Constraints

• \(0 \le M, N, V \le 10^{18}\).

Solution

We present a simple DP solution to this problem.

#include <m3.hpp>

mint solve(ll M, ll N, ll V) {
    // loop invariant: ...
    mint ans = 0;
    for (int i = 59; i >= 0; i--) {
        ll bit_M = M >> i & 1;
        ll bit_N = N >> i & 1;
        ll bit_V = V >> i & 1;
        for (int b1 = 0; b1 <= bit_M; ++b1)
            for (int b2 = 0; b2 <= bit_N; ++b2) 
                if ((b1 xor b2) == bit_V) {
                    if (b1 < bit_M and b2 < bit_N)
                        ans += 1LL << i;
                    else if (b1 < bit_M)
                        ans += (1LL << i) - 1 & N;
                    else if (b2 < bit_N)
                        ans += (1 << i) - 1 & M;
                }
        if ((bit_M xor bit_N) != bit_V)
            return ans;
    }
    return ans + 1;
}