题目描述

给定一个序列

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

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

格式：

输入格式：

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

第2行个字符。

输出格式：

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

样例 1

输入：

5 2

11000

输出：

8

备注

【样例部分数据解释】

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

【数据范围】

对于全部数据满足

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
                    // 01
                    if (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
                    // 先不改
                    // 01
                    dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j][0]) % mod;
                    // 11或者111
                    dp[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);
    }


}

当然，如果上述代码不好理解，我们也可以分多几个状态进行讨论，下面给出了基于8个状态进行讨论的代码：

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();
        // 现在我们分8种情况
        // 0:000
        // 1:001
        // 2:010
        // 3:011
        // 4:100
        // 5:101
        // 6:110(该情况不合法,不予考虑)
        // 7:111
        int[][][] dp = new int[n + 2][k + 1][8];
        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
                    // 先不改
                    // 处理以0结尾的
                    // 000的方案数,应该是之前以00结尾的方案之和
                    dp[i][j][0] = (dp[i][j][0] + (dp[i - 1][j][0] + dp[i - 1][j][4]) % mod) % mod;
                    // 010的方案数,应该是之前以01结尾的方案之和
                    dp[i][j][2] = (dp[i][j][2] + (dp[i - 1][j][1] + dp[i - 1][j][5]) % mod) % mod;
                    // 100的方案数,应该是之前以10结尾的方案之和,其中dp[i - 1][j][6]不合法,不进行统计
                    dp[i][j][4] = (dp[i][j][4] + dp[i - 1][j][2]) % mod;
                    // dp[i][j][6]不合法,不统计
                    // 改的方案数,此时当前值为1
                    // 处理以1结尾的
                    if (j >= 1) {
                        // 001的方案数,应该是之前以00结尾的方案之和
                        dp[i][j][1] = (dp[i][j][1] + (dp[i - 1][j - 1][0] + dp[i - 1][j - 1][4]) % mod) % mod;
                        // 011的方案数,应该是之前以01结尾的方案之和
                        dp[i][j][3] = (dp[i][j][3] + (dp[i - 1][j - 1][1] + dp[i - 1][j - 1][5]) % mod) % mod;
                        // 101的方案数,应该是之前以10结尾的方案之和
                        dp[i][j][5] = (dp[i][j][5] + dp[i - 1][j - 1][2]) % mod;
                        // 111的方案数,应该是之前以11结尾的方案之和
                        dp[i][j][7] = (dp[i][j][7] + (dp[i - 1][j - 1][3] + dp[i - 1][j - 1][7]) % mod) % mod;
                    }
                } else {
                    // 先不改
                    // 此时为1
                    // 处理以1结尾的
                    // 001的方案数,应该是之前以00结尾的方案之和
                    dp[i][j][1] = (dp[i][j][1] + (dp[i - 1][j][0] + dp[i - 1][j][4]) % mod) % mod;
                    // 011的方案数,应该是之前以01结尾的方案之和
                    dp[i][j][3] = (dp[i][j][3] + (dp[i - 1][j][1] + dp[i - 1][j][5]) % mod) % mod;
                    // 101的方案数,应该是之前以10结尾的方案之和
                    dp[i][j][5] = (dp[i][j][5] + dp[i - 1][j][2]) % mod;
                    // 111的方案数,应该是之前以11结尾的方案之和
                    dp[i][j][7] = (dp[i][j][7] + (dp[i - 1][j][3] + dp[i - 1][j][7]) % mod) % mod;
                    // 改的方案数
                    if (j >= 1) {
                        // 处理以0结尾的
                        // 000的方案数,应该是之前以00结尾的方案之和
                        dp[i][j][0] = (dp[i][j][0] + (dp[i - 1][j - 1][0] + dp[i - 1][j - 1][4]) % mod) % mod;
                        // 010的方案数,应该是之前以01结尾的方案之和
                        dp[i][j][2] = (dp[i][j][2] + (dp[i - 1][j - 1][1] + dp[i - 1][j - 1][5]) % mod) % mod;
                        // 100的方案数,应该是之前以10结尾的方案之和,其中dp[i - 1][j][6]不合法,不进行统计
                        dp[i][j][4] = (dp[i][j][4] + dp[i - 1][j - 1][2]) % mod;
                    }
                }
            }
        }
        long result = 0;
        // 问的不大于修改数k的方案数
        for (int i = 0; i <= k; i++) {
            result = (result + (((((((dp[n][i][0] + dp[n][i][1]) % mod + dp[n][i][2]) % mod + dp[n][i][3]) % mod + dp[n][i][4]) % mod + dp[n][i][5]) % mod + dp[n][i][7]) % mod)) % mod;
        }
        System.out.println(result);
    }


}

参考资料：

https://www.matiji.net/exam/brushquestion/4/4498/F16DA07A4D99E21DFFEF46BD18FF68AD