← 查看本卷题目
组合题
#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;}

假设输入的 ss 是包含 nn 个字符的 0101 串，完成下面的判断题和单选题。

第21题判断题原卷 1.5 分

假设数组 dp 长度无限制，函数 solve() 所实现的算法的时间复杂度是 O(n×2m)O(n\times 2^m)。（ ）

填写答案
第22题判断题原卷 1.5 分

输入 11 2 10000000001 时，程序输出两个数 32 和 23。（ ）

填写答案
第23题判断题原卷 2 分

（2 分）在 n≤10n \leq 10 时，solve() 的返回值始终小于 4104^{10}。（ ）

填写答案
第24题单选题原卷 3 分

当 n=10n = 10 且 m=10m = 10 时，有多少种输入使得两行的结果完全一致？（ ）

填写答案
第25题单选题原卷 3 分

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

填写答案
第26题单选题原卷 3 分

若 n=8,m=8n = 8, m = 8，solve 和 solve2 的返回值的最大可能的差值为（ ）？

填写答案