CSP-S 2024 第一轮 第25题：当n〈=6时，solve（)的最大可能返回值为（)

题目

#include <iostream>
#include <string>
using namespace std;

const int P = 998244353, N = 1e4 + 10, M = 20;
int n, m;
string s;
int dp[1 << M];

int solve() {
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = (1 << (m - 1)) - 1; j >= 0; --j) {
            int k = (j << 1) | (s[i] - '0');
            if (j != 0 || s[i] == '1')
                dp[k] = (dp[k] + dp[j]) % P;
        }
    }
    int ans = 0;
    for (int i = 0; i < (1 << m); ++i) {
        ans = (ans + 1ll * i * dp[i]) % P;
    }
    return ans;
}

int solve2() {
    int ans = 0;
    for (int i = 0; i < (1 << n); ++i) {
        int cnt = 0;
        int num = 0;
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                num = num * 2 + (s[j] - '0');
                cnt++;
            }
        }
        if (cnt <= m) (ans += num) %= P;
    }
    return ans;
}

int main() {
    cin >> n >> m;
    cin >> s;
    if (n <= 20) {
        cout << solve2() << endl;
    }
    cout << solve() << endl;
    return 0;
}

假设输入的 $s$ 是包含 $n$ 个字符的 $01$ 串，完成下面的判断题和单选题。

当 $n \leq 6$ 时，solve() 的最大可能返回值为（  ）？

选项

• A. $65$
• B. $211$
• C. $665$
• D. $2059$

答案

C

题解

答案是 C．\(665\)。

solve() 中，dp[j] 表示：从已经处理的字符中，选出一个不含前导零的子序列，其二进制值为 \(j\) 的方案数。这里 dp[0] = 1 表示空序列。

``cpp int k = (j << 1) | (s[i] - '0'); ``

相当于在原二进制数末尾追加当前字符；而条件

``cpp if (j != 0 || s[i] == '1') ``

保证不能用 0 开头。最终返回的是这些子序列的二进制值之和，长度最多为 \(m\)。

怎样让这个和最大？

长度为 \(k\) 的子序列：

• 最多有 \(\binom nk\) 个（按选择的位置区分）；
• 每个的二进制值最多为 \(2^k-1\)，即全部为 1。

因此，当 \(n=6\)、\(m\ge6\)、s = "111111" 时，所有长度的子序列都能被计入，且每一个都取到最大值。

于是最大返回值为 \[ \begin{aligned} \sum_{k=1}^{6}\binom6k(2^k-1) &=\sum_{k=0}^{6}\binom6k2^k-\sum_{k=0}^{6}\binom6k\\ &=(1+2)^6-(1+1)^6\\ &=729-64\\ &=\boxed{665}. \end{aligned} \]

这个值小于模数 \(P\)，所以取模不影响结果。