CSP-S 2024 提高级 第一轮（初赛） 阅读程序（2）

【题目】

CSP-S 2024 提高级 第一轮（初赛） 阅读程序（2）

1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 const int P = 998244353, N = 1e4 + 10, M = 20;
6 int n, m;
7 string s;
8 int dp[1 << M];
9
10 int solve() {
11     dp[0] = 1;
12     for (int i = 0; i < n; i++) {
13         for (int j = (1 << (m - 1)) - 1; j >= 0; j--) {
14             int k = (j << 1) | (s[i] - '0');
15             if (j != 0 || s[i] == '1')
16                 dp[k] = (dp[k] + dp[j]) % P;
17         }
18     }
19     int ans = 0;
20     for (int i = 0; i < (1 << m); i++) {
21         ans = (ans + 1ll * i * dp[i]) % P;
22     }
23     return ans;
24 }
25 int solve2() {
26     int ans = 0;
27     for (int i = 0; i < (1 << n); i++) {
28         int cnt = 0;
29         int num = 0;
30         for (int j = 0; j < n; j++) {
31             if (i & (1 << j)) {
32                 num = num * 2 + (s[j] - '0');
33                 cnt++;
34             }
35         }
36         if (cnt <= m)(ans += num) %= P;
37     }
38     return ans;
39 }
40
41 int main() {
42     cin >> n >> m;
43     cin >> s;
44     if (n <= 20) {
45         cout << solve2() << endl;
46     }
47     cout << solve() << endl;
48     return 0;
49 }

假设输入的 s 是包含 n 个字符的 01 串，完成下面的判断题和单选题：
判断题
1. 函数 solve()所实现的算法时间复杂度是 $O(n\ast 2^m)$。
2. 输入“11 2 10000000001”时，程序输出两个数 32 和 23。
3. 在 n<=10 时，solve()的返回值始终小于$4^{10}$。
单选题
4. 当 n=10 且 m=10 时，有多少种输入使得两行的结果完全一致？
A.1024
B.11
C.10
D.0
5. 当 n<=6 时，solve()的最大可能返回值为？
A.65
B.211
C.665
D.2059
6. 若 n=8，m=8，solve 和 solve2 的返回值的最大可能的差值为？
A.1477
B.1995
C.2059
D.2187

【题目考点】

1. 状压动规

【解题思路】

41 int main() {
42     cin >> n >> m;
43     cin >> s;
44     if (n <= 20) {
45         cout << solve2() << endl;
46     }
47     cout << solve() << endl;
48     return 0;
49 }

先看主函数，n，m是整数，s是一个字符串。
当$n\le 20$时，调用solve2函数

25 int solve2() {
26     int ans = 0;
27     for (int i = 0; i < (1 << n); i++) {
28         int cnt = 0;
29         int num = 0;
30         for (int j = 0; j < n; j++) {
31             if (i & (1 << j)) {
32                 num = num * 2 + (s[j] - '0');
33                 cnt++;
34             }
35         }
36         if (cnt <= m)(ans += num) %= P;
37     }
38     return ans;
39 }

i从0循环到(1<<n)-1，i是状压后的二进制集合状态，枚举所有状态，从n位0循环到n位1。
循环内cnt和num初值为0。
j从0循环到n-1，判断i&(1<<j)，就是判断二进制下i的第j位（从0开始数）是否为1。
num*2+(s[j]-'0')等价于num<<1 | (s[j]-'0')
如果i的第j位为1，那么将num在最低位添加数字s[j]。
j循环结束后，num的值为：从低位到高位遍历，i中有1的位置，就是在s中选择的数字的位置，选出的数字形成二进制数字，就是num。
例：

该例中num为$(110{)}_2$
i指明了在s中选择数字的位置，也就是表示了s中的一个子序列，num为由这个子序列构造出来的数字。
cnt统计的是二进制数i中有多少位是1，如果i中1的位数不超过m，也就是选出的子序列长度不超过m，那么ans增加构造好的num数字，结果模P。
ans为s中所有长度不超过m的子序列构成的数字加和模P。

10 int solve() {
11     dp[0] = 1;
12     for (int i = 0; i < n; i++) {
13         for (int j = (1 << (m - 1)) - 1; j >= 0; j--) {
14             int k = (j << 1) | (s[i] - '0');
15             if (j != 0 || s[i] == '1')
16                 dp[k] = (dp[k] + dp[j]) % P;
17         }
18     }
19     int ans = 0;
20     for (int i = 0; i < (1 << m); i++) {
21         ans = (ans + 1ll * i * dp[i]) % P;
22     }
23     return ans;
24 }

再看solve函数，调用solve函数时，n可能大于20。
i从0~n-1循环，循环中用到了s[i]，可见i是字符串s的下标，因此n的意义应该是字符串s的长度。
j从$2^{m-1}-1$遍历到0，很明显j是二进制集合状态。
根据第20行i从0到$2^m-1$循环，可知集合状态应该有m位。那么j从$2^{m-1}-1$遍历到0，就是在枚举最高位也就是第m-1位为0的所有状态。
集合状态k为：j末尾添加数字s[i]。k比j多一位，因此k是m位二进制数字。
一会儿再研究if判断的意义
状态转移方程为dp[k] = (dp[k]+dp[j])%P
dp[k]在模P意义下增加了dp[j]，结合dp[0]=1，dp[k]的意义应该是求集合状态为k的方案数。问题是dp的下标，也就是集合状态表示了什么？

对于j的某个值jm，记k的值km = (jm<<1)|1，如果s[i1], s[i2], s[i3]…都为1，
那么当i为i1时，s[i1]为’1’，j循环到jm时，dp[km]增加dp[jm]
当i为i2时，s[i2]为’1’，j循环到jm时，dp[km]增加dp[jm]
当i为i3时，s[i3]为’1’，j循环到jm时，dp[km]增加dp[jm]
…

i是s的下标，也就是通过下标i选择s中的数字。选出的数字添加到了已有集合状态j的末尾，形成了新的集合状态k。可以在s中选择不同位置的数字，构造出相同的集合状态。
因此，集合状态k为从s中选出的一些数字，也就是选出一个子序列，前后相接构造成的二进制数字。
dp[k]的意义是从字符串s中选出子序列构造出的二进制数字为k的方案数量。
再看判断if(j != 0 || s[i] == '1')：
如果j == 0 && s[i] == '0'，那么k为0，dp[0]初值为1。而后如果s[i]为’0’，k为j末尾添加0后的值，还是0。由于"0", “00”, “000”，构造出的数字都是0，dp[0]没有办法表示多种选择子序列的方案数，因此dp[0]只能表示空串的方案数，没有表示选出多个0构成的子序列的方案数。
如果k为0，状态转移方程也不会执行，因此有判断if(j != 0 || s[i] == '1')。这会导致dp[k]所表示的子序列的方案数中，不包含有前导0的子序列。

例：如j为0，s[i]为’1’，那么k = (j<<1)|1=1，dp[k] = dp[k]+dp[j] = dp[1]+dp[0] = 1。这一种方案只有选出的子序列为1的情况，不包含01，001，0001等情况，因为dp[0]中没有包含0, 00, 000这些子序列的情况数。

最后集合状态i从0到$2^m-1$循环，枚举m位二进制数字，也就是枚举所有子序列构造出来的数字，每次让ans增加i*dp[i]，也就是dp[i]个i相加。也可以理解为，每选出一个子序列构造出数字i，就把一个数值i加到ans上。
因此ans为s中所有长度不超过m的没有前导0的子序列构成的数字加和模P。

判断题
1. 函数 solve()所实现的算法时间复杂度是 $O(n\ast 2^m)$。
答：T

12     for (int i = 0; i < n; i++) {
13         for (int j = (1 << (m - 1)) - 1; j >= 0; j--) {

外层i循环n次，内层j循环$2^{m-1}$次，总体时间复杂度为$O(n\ast 2^m)$

2. 输入“11 2 10000000001”时，程序输出两个数 32 和 23。
答：T
n=11, m=2, s=“10000000001”
找长度不超过2的子序列
由于是做加和，不用考虑所有数字都是0的子序列。

solve2为长度不超过2的子序列构造数字加和：$1\ast 2+1\ast 9+2\ast 9+3\ast 1=32$
solve为长度不超过2的无前导0子序列构造的数字加和：$1\ast 2+2\ast 9+3\ast 1=23$

当$n\le 20$时
3. 在 n<=10 时，solve()的返回值始终小于$4^{10}$。
答：T
考虑solve的取最大值时，n取最大值为10，s最大时有10位1，即1111111111。

结果为$(2-1)\ast C(9,1)+(2^2-1)\ast C(9,2)+...+(2^{10}-1)\ast C(9,9)<2^{10}(C(9,0)+C(9,1)+...+C(9,9))=2^{10}\ast 2^9=2^{19}<2^{20}=4^{10}$
（根据二项式定理，有$2^n=C(n,0)+...+C(n,n)$）

单选题
4. 当 n=10 且 m=10 时，有多少种输入使得两行的结果完全一致？
A.1024
B.11
C.10
D.0
答：B
若想使solve和solve2的结果一致，则s中有前导0的子序列必须每位都为0，那么字符串的形式必须是由全是1构成的子串和全是0构成的子串连接而成。
字符串长度为10，中1个个数最少是0个，最多是10个，共有11种情况。

5. 当 n<=6 时，solve()的最大可能返回值为？
A.65
B.211
C.665
D.2059
答：
显然，当n=6，且s是6位1，也就是111111时，结果最大。

结果为：$1\ast 6+3\ast 15+7\ast 20+15\ast 15+31\ast 6+63\ast 1=665$

6. 若 n=8，m=8，solve 和 solve2 的返回值的最大可能的差值为？
A.1477
B.1995
C.2059
D.2187
答：C
两函数返回值的差值最大时，有前导0的子序列最多。
在0和1数量已经确定的情况下，应该让字符串s由全为0的子段和全为1的子段连接而成。
01111111 是差值最大的方案，这种情况下，包含前导零的方案正好对应一
个不包含的方案
共$C(7,1)\ast 1+C(7,2)\ast 3+C(7,3)\ast 7+C(7,4)\ast 15+C(7,5)\ast 31+C(7,6)\ast 63+C(7,7)\ast 127=2059$