不是VIP会员,不能显示答案

题目解答

题目:
#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;

}


判断题

1) 假设输入的s 是包含n 个字符的01 串,函数solve()所实现的算法时间复杂度是O(n*2^m)。 ( )

2) 输入“11 2 10000000001”时,程序输出两个数32 和23.( )

3) (2 分)在n<=10 时,solve()的返回值始终小于410( )


选择题

4) 当n=10 且m=10 时,有多少种输入使得两行的结果完全一致?()

5) 当n<=5 时,solve()的最大可能返回值为?( )

6) 若n=8,m=8,solve 和solve2 的返回值的最大可能的差值为( )
考点:
分析:
解答:
评论:
老师: