代码详解：阅读程序-2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-09-07 04:54:49
 * 最后修改: 2025-09-07 04:58:09
 * 文件描述: 2024 CPS-S 第二题
****************************************************************/
#include <iostream>
#include <string>
#include <cstring>   // 为了 memset
using namespace std;

const int P = 998244353; // 取模
const int M = 20;        // m 的上限（由 dp 数组大小决定）
int n, m;
string s;
// dp 的大小是 2^M；下标含义见 solve() 注释
int dp[1 << M];

/*
 * 暴力法：枚举 s 的所有子序列（用位掩码 i 表示选/不选），
 * 计算长度 ≤ m 的子序列的二进制值之和（允许前导 0，空子序列贡献 0）。
 * 复杂度：O(n * 2^n)，因此只在 n 较小（≤20）时调用。
 */
int solve2() {
    int ans = 0;
    // 外层 i 从 0 到 2^n-1，每个 i 的二进制位表示是否选 s[j]
    for (int i = 0; i < (1 << n); ++i) {
        int cnt = 0;   // 选了多少个字符（子序列长度）
        int num = 0;   // 选出的子序列按二进制解释得到的整数值
        // 按原顺序扫描 s 的每一位，保持子序列的相对顺序
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {        // 若选择了第 j 位
                num = num * 2 + (s[j] - '0'); // 将该位作为下一位二进制拼入
                cnt++;
            }
        }
        if (cnt <= m) {                // 只累计长度 ≤ m 的子序列
            ans += num;
            if (ans >= P) ans -= P;    // 等价于 ans = (ans + num) % P，略微快一点
        }
    }
    return ans;
}

//位 DP：只统计“首位必须为 1”的子序列（避免前导 0），长度 ≤ m。
int solve() {
    // 每次调用前清零，只保留 dp[0]=1 作为“空状态”
    // （这是良好习惯；本题单组输入也可依赖全局静态零，但清零更稳妥）
    memset(dp, 0, sizeof(int) * (1 << m));
    dp[0] = 1; // 空子序列的一种方式

    for (int i = 0; i < n; ++i) {            // 按顺序扫描 s 的每一位
        int bit = s[i] - '0';
        // 倒序遍历 j，避免本轮新写入的 dp 值被本轮后续转移再次读取
        for (int j = (1 << (m - 1)) - 1; j >= 0; --j) {
            int k = (j << 1) | bit;          // 将 bit 作为最低位拼接到 j 的右侧
            // 当 j==0 且 bit==0 时，代表“尝试以 0 开头”，被禁止（避免前导 0）
            if (j != 0 || bit == 1) {
                dp[k] += dp[j];
                if (dp[k] >= P) dp[k] -= P;  // 取模
            }
        }
    }

    // 以“数值 i × 方案数 dp[i]”的方式加权求和
    long long ans = 0;
    for (int i = 0; i < (1 << m); ++i) {
        ans = (ans + 1LL * i * dp[i]) % P;
    }
    return (int)ans;
}

int main() {
    cin >> n >> m;
    cin >> s;

    // 当 n 较小（≤20）时，输出暴力校验值（solve2）
    if (n <= 20) {
        cout << solve2() << '\n';
    }

    // 输出位 DP 的值（只统计首位为 1 的合法子序列）
    cout << solve() << '\n';
    return 0;
}