... ~~~~~

#include <vector>
#include <cstdint>
#include <algorithm>
#include <limits>

using namespace std;

const int SHIFT_MAX = 60;
const int MAX_OP = 60;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const unsigned long long INF_COST = numeric_limits<unsigned long long>::max();
    vector<vector<unsigned long long>> dp(SHIFT_MAX + 1, vector<unsigned long long>(SHIFT_MAX + 1, INF_COST));
    dp[0][0] = 0;

    for (int op = 1; op <= MAX_OP; op++) {
        vector<vector<unsigned long long>> next_dp = dp;
        for (int i = 0; i <= SHIFT_MAX; i++) {
            for (int j = 0; j <= SHIFT_MAX; j++) {
                if (dp[i][j] == INF_COST) continue;
                if (i + op <= SHIFT_MAX) {
                    next_dp[i + op][j] = min(next_dp[i + op][j], dp[i][j] + (1ULL << op));
                }
                if (j + op <= SHIFT_MAX) {
                    next_dp[i][j + op] = min(next_dp[i][j + op], dp[i][j] + (1ULL << op));
                }
            }
        }
        dp = move(next_dp);
    }

    struct Combination { int shiftX, shiftY; unsigned long long cost; };
    vector<Combination> combos;
    for (int i = 0; i <= SHIFT_MAX; i++) {
        for (int j = 0; j <= SHIFT_MAX; j++) {
            if (dp[i][j] != INF_COST) {
                combos.push_back({i, j, dp[i][j]});
            }
        }
    }

    int T;
    cin >> T;
    while (T--) {
        unsigned long long X, Y;
        cin >> X >> Y;
        if (X == Y) {
            cout << 0 << "\n";
            continue;
        }
        unsigned long long best = INF_COST;
        for (auto &combo : combos) {
            unsigned long long newX = X >> combo.shiftX;
            unsigned long long newY = Y >> combo.shiftY;
            if (newX == newY) {
                best = min(best, combo.cost);
            }
        }
        cout << best << "\n";
    }

    return 0;
}

~~~~~

codeforce C?#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int numColors, numElements;
        cin >> numColors >> numElements;
        
        vector<int> frequency(numColors + 1, 0);
        vector<int> colors(numElements);
        
        for (int i = 0; i < numElements; i++) {
            cin >> colors[i];
            frequency[colors[i]]++;
        }

        vector<int> cumCount(numColors + 2, 0);
        for (int i = numColors; i >= 1; i--) {
            cumCount[i] = frequency[i] + cumCount[i + 1];
        }

        long long answer = 0;
        for (int splitIndex = 1; splitIndex < numColors; splitIndex++) {
            int leftCount = cumCount[splitIndex];
            int rightCount = cumCount[numColors - splitIndex];
            int commonCount = cumCount[max(splitIndex, numColors - splitIndex)];
            answer += static_cast<long long>(leftCount) * rightCount - commonCount;
        }

        cout << answer << "\n";
    }
    
    return 0;
}

...

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

long long modexp(long long base, long long exp, long long mod = MOD) {
    long long res = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

long long computeR(long long A, long long B) {
    int LA = 0, LB = 0;
    {
        long long temp = A;
        while (temp > 0) {
            LA++;
            temp /= 2;
        }
        if (LA == 0) LA = 1;
    }
    {
        long long temp = B;
        while (temp > 0) {
            LB++;
            temp /= 2;
        }
        if (LB == 0) LB = 1;
    }

    int L = max(LA, LB);
    vector<int> A_bits(L, 0), B_bits(L, 0);

    for (int i = 0; i < L; i++) {
        A_bits[i] = (A >> (L - 1 - i)) & 1;
        B_bits[i] = (B >> (L - 1 - i)) & 1;
    }

    vector<vector<long long>> dp(L + 1, vector<long long>(16, 0));
    dp[0][0] = 1;

    for (int pos = 0; pos < L; pos++) {
        for (int state = 0; state < 16; state++) {
            long long ways = dp[pos][state];
            if (!ways) continue;

            int fx = (state >> 0) & 1;
            int fu = (state >> 1) & 1;
            int fy = (state >> 2) & 1;
            int fv = (state >> 3) & 1;

            int bitA = A_bits[pos];
            int bitB = B_bits[pos];

            for (int a = 0; a < 2; a++) {
                for (int b = 0; b < 2; b++) {
                    int xorVal = a ^ b;
                    for (int c = 0; c < 2; c++) {
                        int d = c ^ xorVal;

                        if (!fx && a > bitA) continue;
                        int nfx = fx | (a < bitA);
                        if (!fu && b > bitA) continue;
                        int nfu = fu | (b < bitA);
                        if (!fy && c > bitB) continue;
                        int nfy = fy | (c < bitB);
                        if (!fv && d > bitB) continue;
                        int nfv = fv | (d < bitB);

                        int nstate = (nfx) | (nfu << 1) | (nfy << 2) | (nfv << 3);
                        dp[pos + 1][nstate] = (dp[pos + 1][nstate] + ways) % MOD;
                    }
                }
            }
        }
    }

    long long R = 0;
    for (int s = 0; s < 16; s++) {
        R = (R + dp[L][s]) % MOD;
    }

    return R;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    long long inv2 = modexp(2, MOD - 2, MOD);
    long long inv4 = modexp(4, MOD - 2, MOD);

    while (t--) {
        long long n, m, A, B;
        cin >> n >> m >> A >> B;

        long long constA = (A + 1) % MOD;
        long long constB = (B + 1) % MOD;

        long long combA = (((A + 1) % MOD) * (A % MOD)) % MOD;
        combA = (combA * inv2) % MOD;

        long long combB = (((B + 1) % MOD) * (B % MOD)) % MOD;
        combB = (combB * inv2) % MOD;

        long long p2n = (modexp(2, n, MOD) - 2 + MOD) % MOD;
        long long p2m = (modexp(2, m, MOD) - 2 + MOD) % MOD;

        long long case1 = (constA * constB) % MOD;
        long long case2a = (constA * ((combB * p2m) % MOD)) % MOD;
        long long case2b = (constB * ((combA * p2n) % MOD)) % MOD;

        long long R = computeR(A, B);
        long long diffTerm = (R - (((A + 1) % MOD * (B + 1) % MOD) % MOD) + MOD) % MOD;
        diffTerm = (diffTerm * inv4) % MOD;

        long long case3 = (((p2n * p2m) % MOD) * diffTerm) % MOD;
        long long ans = (case1 + case2a + case2b + case3) % MOD;

        cout << ans % MOD << "\n";
    }

    return 0;
}

...

... ~~~~~

#include <vector>
#include <cstdint>
#include <algorithm>
#include <limits>

using namespace std;

const int SHIFT_MAX = 60;
const int MAX_OP = 60;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const unsigned long long INF_COST = numeric_limits<unsigned long long>::max();
    vector<vector<unsigned long long>> dp(SHIFT_MAX + 1, vector<unsigned long long>(SHIFT_MAX + 1, INF_COST));
    dp[0][0] = 0;

    for (int op = 1; op <= MAX_OP; op++) {
        vector<vector<unsigned long long>> next_dp = dp;
        for (int i = 0; i <= SHIFT_MAX; i++) {
            for (int j = 0; j <= SHIFT_MAX; j++) {
                if (dp[i][j] == INF_COST) continue;
                if (i + op <= SHIFT_MAX) {
                    next_dp[i + op][j] = min(next_dp[i + op][j], dp[i][j] + (1ULL << op));
                }
                if (j + op <= SHIFT_MAX) {
                    next_dp[i][j + op] = min(next_dp[i][j + op], dp[i][j] + (1ULL << op));
                }
            }
        }
        dp = move(next_dp);
    }

    struct Combination { int shiftX, shiftY; unsigned long long cost; };
    vector<Combination> combos;
    for (int i = 0; i <= SHIFT_MAX; i++) {
        for (int j = 0; j <= SHIFT_MAX; j++) {
            if (dp[i][j] != INF_COST) {
                combos.push_back({i, j, dp[i][j]});
            }
        }
    }

    int T;
    cin >> T;
    while (T--) {
        unsigned long long X, Y;
        cin >> X >> Y;
        if (X == Y) {
            cout << 0 << "\n";
            continue;
        }
        unsigned long long best = INF_COST;
        for (auto &combo : combos) {
            unsigned long long newX = X >> combo.shiftX;
            unsigned long long newY = Y >> combo.shiftY;
            if (newX == newY) {
                best = min(best, combo.cost);
            }
        }
        cout << best << "\n";
    }

    return 0;
}

~~~~~

codeforce C?#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int numColors, numElements;
        cin >> numColors >> numElements;
        
        vector<int> frequency(numColors + 1, 0);
        vector<int> colors(numElements);
        
        for (int i = 0; i < numElements; i++) {
            cin >> colors[i];
            frequency[colors[i]]++;
        }

        vector<int> cumCount(numColors + 2, 0);
        for (int i = numColors; i >= 1; i--) {
            cumCount[i] = frequency[i] + cumCount[i + 1];
        }

        long long answer = 0;
        for (int splitIndex = 1; splitIndex < numColors; splitIndex++) {
            int leftCount = cumCount[splitIndex];
            int rightCount = cumCount[numColors - splitIndex];
            int commonCount = cumCount[max(splitIndex, numColors - splitIndex)];
            answer += static_cast<long long>(leftCount) * rightCount - commonCount;
        }

        cout << answer << "\n";
    }
    
    return 0;
}

...

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

long long modexp(long long base, long long exp, long long mod = MOD) {
    long long res = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

long long computeR(long long A, long long B) {
    int LA = 0, LB = 0;
    {
        long long temp = A;
        while (temp > 0) {
            LA++;
            temp /= 2;
        }
        if (LA == 0) LA = 1;
    }
    {
        long long temp = B;
        while (temp > 0) {
            LB++;
            temp /= 2;
        }
        if (LB == 0) LB = 1;
    }

    int L = max(LA, LB);
    vector<int> A_bits(L, 0), B_bits(L, 0);

    for (int i = 0; i < L; i++) {
        A_bits[i] = (A >> (L - 1 - i)) & 1;
        B_bits[i] = (B >> (L - 1 - i)) & 1;
    }

    vector<vector<long long>> dp(L + 1, vector<long long>(16, 0));
    dp[0][0] = 1;

    for (int pos = 0; pos < L; pos++) {
        for (int state = 0; state < 16; state++) {
            long long ways = dp[pos][state];
            if (!ways) continue;

            int fx = (state >> 0) & 1;
            int fu = (state >> 1) & 1;
            int fy = (state >> 2) & 1;
            int fv = (state >> 3) & 1;

            int bitA = A_bits[pos];
            int bitB = B_bits[pos];

            for (int a = 0; a < 2; a++) {
                for (int b = 0; b < 2; b++) {
                    int xorVal = a ^ b;
                    for (int c = 0; c < 2; c++) {
                        int d = c ^ xorVal;

                        if (!fx && a > bitA) continue;
                        int nfx = fx | (a < bitA);
                        if (!fu && b > bitA) continue;
                        int nfu = fu | (b < bitA);
                        if (!fy && c > bitB) continue;
                        int nfy = fy | (c < bitB);
                        if (!fv && d > bitB) continue;
                        int nfv = fv | (d < bitB);

                        int nstate = (nfx) | (nfu << 1) | (nfy << 2) | (nfv << 3);
                        dp[pos + 1][nstate] = (dp[pos + 1][nstate] + ways) % MOD;
                    }
                }
            }
        }
    }

    long long R = 0;
    for (int s = 0; s < 16; s++) {
        R = (R + dp[L][s]) % MOD;
    }

    return R;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    long long inv2 = modexp(2, MOD - 2, MOD);
    long long inv4 = modexp(4, MOD - 2, MOD);

    while (t--) {
        long long n, m, A, B;
        cin >> n >> m >> A >> B;

        long long constA = (A + 1) % MOD;
        long long constB = (B + 1) % MOD;

        long long combA = (((A + 1) % MOD) * (A % MOD)) % MOD;
        combA = (combA * inv2) % MOD;

        long long combB = (((B + 1) % MOD) * (B % MOD)) % MOD;
        combB = (combB * inv2) % MOD;

        long long p2n = (modexp(2, n, MOD) - 2 + MOD) % MOD;
        long long p2m = (modexp(2, m, MOD) - 2 + MOD) % MOD;

        long long case1 = (constA * constB) % MOD;
        long long case2a = (constA * ((combB * p2m) % MOD)) % MOD;
        long long case2b = (constB * ((combA * p2n) % MOD)) % MOD;

        long long R = computeR(A, B);
        long long diffTerm = (R - (((A + 1) % MOD * (B + 1) % MOD) % MOD) + MOD) % MOD;
        diffTerm = (diffTerm * inv4) % MOD;

        long long case3 = (((p2n * p2m) % MOD) * diffTerm) % MOD;
        long long ans = (case1 + case2a + case2b + case3) % MOD;

        cout << ans % MOD << "\n";
    }

    return 0;
}

...