题解 | #E. 小红的漂亮串#

小红的漂亮串

https://ac.nowcoder.com/acm/contest/69695/E

欢迎关注

珂朵莉牛客周赛专栏

珂朵莉牛客小白月赛专栏

E. 小红的漂亮串

一眼状压DP

这题有'red', 'der'限制，所以直接想O(1)求容斥解，行不通.

如何n很大的话，需要矩阵幂优化。

回到状压的思路

引入5种状态

0, any是1,2,3,4以外的所有状态
1, 以r字母结尾
2，以d字母结尾
3，以re字母结尾
4，以de字母结尾

先聊下如何解决

Q: 子串不包含‘der’

只要在递推过程中, 对der的状态构造忽略即可

Q: 需要包含至少一个‘red’

额外引入一维的状态0/1, 表示当前字符串以包含red, 和暂时不包含red

设计好了状态, 以及解决思路

来看一下如何设计状态转移

令 dp[2][5], 前一维表示是否包含'red', 后一维表示以什么结尾的状态

DP递推的话，以下两种都可以

填表法
刷表法

为啥要两者都介绍下呢？

主要是如果某一种实现，遇到了wa，这个时候可以用另一种思路去check/verify, 看看哪里的转移有遗漏。

状态迁移还是太多，这边选用一个 (0, 3)来分析，它涉及一个阶级跃迁

alt

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();

        // any
        // r, d
        // re, de,
        long mod = 10_0000_0007l;

        // red, der
        long[][] dp = new long[2][5];
        dp[0][0] = 24;
        dp[0][1] = dp[0][2] = 1;

        for (int i = 1; i < n; i++) {
            long[][] dp2 = new long[2][5];

            // 不包含red字符串(在本身的圈子内转移)
            dp2[0][0] = (dp[0][0] * 24 % mod + dp[0][1] * 23 % mod + dp[0][2] * 23 % mod + dp[0][3] * 24 % mod + dp[0][4] * 24 % mod) % mod;
            dp2[0][1] = (dp[0][0] + dp[0][1] + dp[0][2] + dp[0][3]) % mod;
            dp2[0][2] = (dp[0][0] + dp[0][1] + dp[0][2] + dp[0][4]) % mod;
            dp2[0][3] = dp[0][1];
            dp2[0][4] = dp[0][2];

            // 包含red字符串(在本身的圈子内转移)
            dp2[1][0] = (dp[1][0] * 24 % mod + dp[1][1] * 23 % mod + dp[1][2] * 23 % mod + dp[1][3] * 24 % mod + dp[1][4] * 24 % mod) % mod;
            dp2[1][1] = (dp[1][0] + dp[1][1] + dp[1][2] + dp[1][3]) % mod;
            dp2[1][2] = (dp[1][0] + dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4]) % mod;
            dp2[1][3] = dp[1][1];
            dp2[1][4] = dp[1][2];
            
            // 非常俏皮的阶级跃迁(最特别)，单独拎出来
            dp2[1][2] = (dp2[1][2] + dp[0][3]) % mod;

            dp = dp2;
        }

        // 只累加包含red字符串的状态
        long res = 0;
        for (int i = 0; i < 5; i++) {
            res += dp[1][i];
            res %= mod;
        }
        System.out.println(res);
    }

}

矩阵幂

把上边的2x5 压缩为一维

然后构建一个10x10的转移矩阵

在n很大情况下，这可能是唯一解

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();

        long mod = 10_0000_0007l;

        long[][] translate = new long[][] {
            {24, 23, 23, 24, 24, 0, 0, 0, 0, 0},
            {1, 1, 1, 1, 0, 0, 0, 0, 0, 0},
            {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
            {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 24, 23, 23, 24, 24},
            {0, 0, 0, 0, 0, 1, 1, 1, 1, 0},
            {0, 0, 0, 1, 0, 1, 1, 1, 1, 1},
            {0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
        };

        Matrix matrix = new Matrix(translate);
        Matrix matrix2 = Matrix.quickPow(matrix, n, mod);

        Matrix vec = new Matrix(new long[][] {{1}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}});
        Matrix res = matrix2.mul(vec, mod);

        long ans = 0;
        for (int i = 5; i < 10; i++) {
            ans += res.arr[i][0];
            ans %= mod;
        }
        System.out.println(ans);
    }

    static 
    class Matrix {
        long[][] arr;
        int r, c;
        Matrix(long[][] arr) {
            this.arr = arr;
            this.r = arr.length;
            this.c = arr[0].length;
        }

        Matrix mul(Matrix other, long mod) {
            int nr = this.r, nc = other.c;
            long[][] res = new long[nr][nc];
            for (int i = 0; i < nr; i++) {
                for (int j = 0; j < nc; j++) {
                    long temp = 0;
                    for (int k = 0; k < c; k++) {
                        temp = (temp + arr[i][k] * other.arr[k][j] % mod) % mod;
                    }
                    res[i][j] = temp;
                }
            }
            return new Matrix(res);
        }

        static Matrix E(int n) {
            long[][] arr = new long[n][n];
            for (int i = 0; i < n; i++) {
                arr[i][i] = 1;
            }
            return new Matrix(arr);
        }

        static Matrix quickPow(Matrix base, long k, long mod) {
            Matrix r = Matrix.E(base.r);
            while (k > 0) {
                if (k % 2 == 1) {
                    r = r.mul(base, mod);
                }
                k /= 2;
                base = base.mul(base, mod);
            }
            return r;
        }
    }

}