CSP-S 2024 第一轮 第26题：若 n =8，m = 8，solve 和 solve2 的返回值的最大可能的差值

题目

#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 = 8, m = 8$，solve 和 solve2 的返回值的最大可能的差值为（  ）？

选项

• A. $1477$
• B. $1995$
• C. $2059$
• D. $2187$

答案

C

题解

答案是 C，\(2059\)，在 \(s=\texttt{01111111}\) 时取得。

关键在于：solve 漏掉了以 0 开头的子序列，solve2 则全部统计。这里子序列按选取的下标区分。

solve 中，dp[j] 记录二进制值为 \(j\) 的子序列数量，追加一位后变成：

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

但下面的判断禁止从空序列开始选一个 0：

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

所以，令 \[ D=\operatorname{solve2}()-\operatorname{solve}(), \] 则 \(D\) 就是所有以 0 开头的子序列的数值之和。本题 \(n=m=8\)，长度限制不起作用，数值也远小于模数。

为什么最大值在 01111111 取得？

先说明：如果串中有多个 0，把第一个 0 之后的任意一个 0 改成 1，一定能增大 \(D\)。

设被修改的位置后面有 \(k\) 位：

• 对于以更早的 0 开头、且选中该位置的子序列，修改会增大数值。固定一个更早的 0 作为开头，仅考虑这些子序列，增量就有

\[ \sum_{t=0}^{k}\binom kt2^t=3^k. \]

• 原本以被修改位置的 0 开头的子序列，现在不再计入 \(D\)。损失最多是后面 \(k\) 位全为 1 时的子序列数值之和：

\[ \sum_{t=0}^{k}\binom kt(2^t-1)=3^k-2^k. \]

增量大于损失，因此最大值对应的串只有一个 0。

只有一个 0 时，它前面的 1 对 \(D\) 没有贡献；它后面的 1 越多，\(D\) 越大。因此应把这个 0 放在最前面，得到 01111111。

此时漏掉的子序列都选了开头的 0，再从后面七个 1 中选取 \(t\) 个，数值为 \(2^t-1\)。所以

\[ \boxed{ D_{\max} =\sum_{t=0}^{7}\binom7t(2^t-1) =3^7-2^7 =2187-128 =2059 }. \]