Xperi

01Count Integer Sequences

Print the number of integer sequences of length N, A = {A1, A2, A3...., AN} possible where the Sequence A should follow the conditions below:

All elements in A should be between 0 and M (inclusive)
XOR of all the elements in A is equal to X Print the number of integer sequence satisfying these conditions modulo 998244353. Input Format: N, M , X Function Description Complete the function countIntegerSequences in the editor. countIntegerSequences has the following parameters:
N: the length of the sequence
M: the maximum value of the elements in the sequence
X: the XOR value to be achieved Returns int: the number of integer sequences modulo 998244353

Constraints

N/A

数位 DP 按位处理。设 f[i][tight][xor_so_far] 但状态太大，所以更优做法：按位独立。每位 b(0..log M)：当前位有 K=M+1 个可选值中的"该位为 0/1"的数量，前 N-1 个元素自由(XOR 可任意)，最后一个被前面唯一确定。注意 M+1 不一定是 2 的幂，需要按位拆分用经典 digit DP。完整解法用按位的概率/计数：构造长度 N 的序列 XOR=X 等价于：自由选前 N-1 个 ∈[0,M]，最后一个 = X XOR(前N-1)，但需校验它也在 [0,M]。即答案 = #序列 of length N-1 over [0,M] s.t. their XOR XOR X ∈ [0, M]。可用 DP dp[i][x] = i 个数 XOR 等于 x 的方案数。状态 ≤ N · 2^ceil(log(max(M,X)))。

MOD = 998244353

def countIntegerSequences(N: int, M: int, X: int) -> int:
    # bit length needed
    L = max(M, X).bit_length()
    sz = 1 << L
    dp = [0] * sz
    dp[0] = 1
    for _ in range(N - 1):
        ndp = [0] * sz
        for x in range(sz):
            if dp[x] == 0:
                continue
            for v in range(M + 1):
                ndp[x ^ v] = (ndp[x ^ v] + dp[x]) % MOD
        dp = ndp
    ans = 0
    for x in range(sz):
        last = X ^ x
        if 0 <= last <= M:
            ans = (ans + dp[x]) % MOD
    return ans if N >= 1 else (1 if X == 0 else 0)

class Solution {
    static final int MOD = 998244353;

    int countIntegerSequences(int N, int M, int X) {
        int L = Math.max(32 - Integer.numberOfLeadingZeros(Math.max(M, X)), 1);
        int sz = 1 << L;
        long[] dp = new long[sz];
        dp[0] = 1;
        for (int step = 0; step < N - 1; step++) {
            long[] ndp = new long[sz];
            for (int x = 0; x < sz; x++) {
                if (dp[x] == 0) continue;
                for (int v = 0; v <= M; v++) {
                    ndp[x ^ v] = (ndp[x ^ v] + dp[x]) % MOD;
                }
            }
            dp = ndp;
        }
        long ans = 0;
        for (int x = 0; x < sz; x++) {
            int last = X ^ x;
            if (last >= 0 && last <= M) ans = (ans + dp[x]) % MOD;
        }
        return (int) ans;
    }
}

class Solution {
public:
    static const int MOD = 998244353;

    int countIntegerSequences(int N, int M, int X) {
        int top = max(M, X);
        int L = 1;
        while ((1 << L) <= top) L++;
        int sz = 1 << L;
        vector<long long> dp(sz, 0);
        dp[0] = 1;
        for (int step = 0; step < N - 1; step++) {
            vector<long long> ndp(sz, 0);
            for (int x = 0; x < sz; x++) {
                if (dp[x] == 0) continue;
                for (int v = 0; v <= M; v++) {
                    ndp[x ^ v] = (ndp[x ^ v] + dp[x]) % MOD;
                }
            }
            dp = ndp;
        }
        long long ans = 0;
        for (int x = 0; x < sz; x++) {
            int last = X ^ x;
            if (last >= 0 && last <= M) ans = (ans + dp[x]) % MOD;
        }
        return (int) ans;
    }
};

02Make Numbers Equal

There are two numbers number A and number B. Your task

Constraints

N/A

Example 1

Input:

A = 7
B = 9

Output:

Explanation: Operation 1: B > A so B = 9 - 7 = 2 Operation 2: A > B so A = 7 - 2 = 5 Operation 3: A > B so A = 5 - 2 = 3 Operation 4: A > B so A = 3 - 2 = 1 Operation 5: B > A so B = 2 - 1 = 1 A and B are equal so we stop cost = 5.

解法

观察过程：用大数减去小数若干次直到余数。这其实是欧几里得算法的步数总和。cost(A, B) = A//B + cost(B, A%B)，递归直到一方为 0；最终 A==B 即 gcd(A,B)，所以 B>0 时一直递归，最后多减一次会等于 0，我们停在 A==B(即上一步前最小值等于 gcd)。实际：累计 A//B 然后递归 (B, A%B)，base case 是 A % B == 0 时停止并减少 1(最后一次会过头)。时间复杂度 O(log min(A,B))。

def makeNumbersEqual(A: int, B: int) -> int:
    cost = 0
    while A and B:
        if A < B:
            A, B = B, A
        cost += A // B
        A %= B
        if A == 0:
            cost -= 1
            break
    return cost

class Solution {
    long makeNumbersEqual(long A, long B) {
        long cost = 0;
        while (A > 0 && B > 0) {
            if (A < B) { long t = A; A = B; B = t; }
            cost += A / B;
            A %= B;
            if (A == 0) { cost--; break; }
        }
        return cost;
    }
}

class Solution {
public:
    long long makeNumbersEqual(long long A, long long B) {
        long long cost = 0;
        while (A > 0 && B > 0) {
            if (A < B) swap(A, B);
            cost += A / B;
            A %= B;
            if (A == 0) { cost--; break; }
        }
        return cost;
    }
};