问题描述 给定正整数$N$和$K$。求所有不超过$N$且满足以下条件的正整数$x$的总和，对$998244353$取模：$x$的二进制表示中$1$的个数恰好为$K$。给定$T$个测试用例，请分别求解。 c++code

以下是使用C++实现的代码，解决您提出的问题。我们将通过动态规划（Dynamic Programming, DP）来高效计算满足条件的正整数$x$的总和。 ```cpp #include <bits/stdc++.h> using namespace std; const int MOD = 998244353; // dp[i][j] 表示用i位二进制数构成且有j个1的所有数的总和 long long dp[32][32]; // cnt[i][j] 表示用i位二进制数构成且有j个1的数的个数 long long cnt[32][32]; void precompute(int max_bits, int max_ones) { // 初始化 for (int i = 0; i <= max_bits; ++i) { for (int j = 0; j <= max_ones; ++j) { dp[i][j] = 0; cnt[i][j] = 0; } } // 边界条件 cnt[0][0] = 1; // 用0位表示0个1，只有1种方法 for (int i = 1; i <= max_bits; ++i) { for (int j = 0; j <= max_ones; ++j) { if (j >= 1) { // 当前位为1的情况 dp[i][j] = (dp[i - 1][j - 1] + cnt[i - 1][j - 1] * ((1LL << (i - 1)) % MOD)) % MOD; cnt[i][j] = (cnt[i][j] + cnt[i - 1][j - 1]) % MOD; } // 当前位为0的情况 dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD; cnt[i][j] = (cnt[i][j] + cnt[i - 1][j]) % MOD; } } } long long solve(long long N, int K) { if (K == 0) return 0; // 如果需要的1的个数为0，则总和为0 vector<int> bits; while (N > 0) { bits.push_back(N % 2); N /= 2; } int n = bits.size(); long long result = 0; int ones = 0; for (int i = n - 1; i >= 0; --i) { if (bits[i] == 1) { // 如果当前位是1，考虑将其设为0的情况 if (ones + 1 <= K) { if (ones + 1 == K) { result = (result + (cnt[i][K - ones - 1] * (1LL << i)) % MOD) % MOD; } else { result = (result + dp[i][K - ones - 1]) % MOD; } } ones += 1; } if (ones > K) break; } if (ones == K) result = (result + 1) % MOD; // 考虑N本身是否符合条件 return result; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; precompute(31, 31); // 预处理最多31位的情况 while (T--) { long long N; int K; cin >> N >> K; cout << solve(N, K) << "\n"; } return 0; } ``` ### 解释 1. **动态规划预处理**： - `dp[i][j]`：表示用`i`位二进制数构成且有`j`个`1`的所有数的总和。 - `cnt[i][j]`：表示用`i`位二进制数构成且有`j`个`1`的数的个数。 - 我们通过递推公式预处理出所有可能的`dp[i][j]`和`cnt[i][j]`值。 2. **核心逻辑**： - 对于每个测试用例，我们先将`N`转化为二进制形式。 - 然后从最高位开始遍历，对于每一位判断其是否为`1`。如果是`1`，则考虑将其设为`0`的情况，并根据预处理的结果累加答案。 3. **取模操作**： - 由于结果可能非常大，我们在每一步都对`998244353`取模以避免溢出。 4. **时间复杂度**： - 预处理的时间复杂度为`O(max_bits * max_ones)`。 - 每个测试用例的查询复杂度为`O(log N)`。 ###