当前位置：首页 > news >正文

2024百度之星：BD202404 110串

news 2025/6/28 7:52:59

题目描述

给定一个 $01$ 序列 $a_1a_2\ldots a_n,a_i\in \{0,1\}$

我们可以修改该序列的任意一个数字，可以将 $0$ 变成 $1$ ，也可以将 $1$ 变成 $0$ ，注意不能删除或增加数字。

请问，修改不超过 $k$ 个数字能让给定的序列中不含有特定的一个子串 $110$ 的方案数有多少种，由于答案很大输出对 $998244353$ 以后的结果即可。

格式：

输入格式：

第1行2个整数 $n, k$ ，表示 $01$ 序列的长度和最多可修改的数字个数。

第2行 $n$ 个字符 $a_1a_2\ldots a_n,a_i\in \{0,1\}$ 。

输出格式：

输出 $1$ 行，表示修改不超过 $k$ 个数字让给定的序列中不含有 110的方案数对 $998244353$ 以后的结果。

样例 1

输入：

5 2

11000

输出：

备注

【样例部分数据解释】

共有01000,10000,00000,10100,10010,10001,01001,01010这几种情况。

【数据范围】

对于全部数据满足 $1\le n\le 5000,0\le k \le 5000$

AC代码及其注释

import java.util.Scanner;public class Main {public static void main(String[] args) {int mod = 998244353;Scanner sc = new Scanner(System.in);// 序列的长度int n = sc.nextInt();// 可修改的次数int k = sc.nextInt();String str = sc.next();char[] strChar = str.toCharArray();sc.close();// 3种状态,0:0结尾(000,010,100,110(x)),1:1(001,101),2:11(011,111),其实还可以设一个不合法状态,但感觉用不上int[][][] dp = new int[n + 2][k + 1][3];dp[0][0][0] = 1;
//        dp[0][0][1] = 1;
//        dp[0][0][2] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j <= k; j++) {if (strChar[i - 1] == '0') {// 为0// 先不改dp[i][j][0] = (dp[i][j][0] + (dp[i - 1][j][0] + dp[i - 1][j][1]) % mod) % mod;// 改的方案数,此时当前值为1// 01if (j >= 1) {dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j - 1][0]) % mod;// 11或者111,其实都一样dp[i][j][2] = (dp[i][j][2] + (dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2]) % mod) % mod;}} else {// 此时为1// 先不改// 01dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j][0]) % mod;// 11或者111dp[i][j][2] = (dp[i][j][2] + (dp[i - 1][j][1] + dp[i - 1][j][2]) % mod) % mod;// 改的方案数if (j >= 1) {dp[i][j][0] = (dp[i][j][0] + (dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1]) % mod) % mod;}}}}long result = 0;for (int i = 0; i <= k; i++) {result = (result + ((dp[n][i][0] + dp[n][i][1])%mod + dp[n][i][2])%mod)%mod;}System.out.println(result);}}