1246（digits）

【題目描述】 1,2,4,6 這四個(gè)數(shù)字有一個(gè)神奇的性質(zhì)：如果將其分別取以 2 為底的冪，得到的分別是 2,4,16,64，仍是由這四個(gè)數(shù)字組成的。我們從數(shù)字串1 開始，每秒鐘它的每一位都會(huì)獨(dú)立地變成 2 的冪。

例如，在前幾秒鐘，數(shù)字串會(huì)依次變成：

1. 2
2. 4
3. 16
4. 264
5. 46416
6. 166416264
7. 264641626446416
8. 46416641626446416166416264
9. 166416264641626446416166416264264641626446416

顯然，這些數(shù)字串都僅包含 1,2,4,6 這四個(gè)數(shù)字。輸入整數(shù) n 和數(shù)字串 S，請你求出 S 在第 n 秒鐘的數(shù)字串共出現(xiàn)了幾次？由于答案可能很大，只需要你輸出它對 998244353 取模的結(jié)果。

【輸入格式】 從標(biāo)準(zhǔn)輸入讀入數(shù)據(jù)。包含兩行，第一行為一個(gè)數(shù) n，第二行為一個(gè)串 S。
【輸出格式】 輸出到標(biāo)準(zhǔn)輸出。僅有一行，含有一個(gè)整數(shù)，表示所求的答案。

【樣例 1 輸入】

9
26

【樣例 1 輸出】

5

【樣例 1 解釋】
第 9 秒的數(shù)字串為166416264641626446416166416264264641626446416，其中出現(xiàn)了5 次26。

【樣例 2 輸入】

2020
16

【樣例 2 輸出】

292008622

【數(shù)據(jù)范圍】

image.png

破題思路

1. 按數(shù)位變化，我們可以基于數(shù)位思考；N = 10^9，時(shí)間復(fù)雜度要就是log(n)；
2. 基本上1個(gè)數(shù)位大概率會(huì)變2個(gè)。如果模擬法，沒迭代一秒，字符串長度是指數(shù)增加的?？梢赃^前8組測試。（可以寫一下，快速拿分，并且在之后，用作新算法的基準(zhǔn)測試用例對拍）
3. 所有數(shù)位都跳不出（1,2,4,6）這個(gè)集合。如果不考慮位置信息，其實(shí)就是一個(gè)線性遞推問題。

dp[i][1] -> dp[i+1][2]
dp[i][2] -> dp[i+1][4]
dp[i][4] -> dp[i+1][1], dp[i+1][6]
dp[i][6] -> dp[i+1][6], dp[i+1][4]

把4個(gè)數(shù)字做一個(gè)離散化，變成(0,1,2,3)之后，很容易可以構(gòu)建變換矩陣, 如果不知道怎么根據(jù)線性遞推的DP公式如何寫出變換矩陣，可以先學(xué)習(xí)我這篇博客。DP的五類優(yōu)化(2) - 快速冪，四邊形不等式

0 1 0 0 
0 0 1 0
1 0 0 1
0 0 1 1

然后就是一個(gè)矩陣快速冪的模板
隨后我們可以過掉所有|S| = 1的測試數(shù)據(jù)了。

4. 如果|S| > 1，我第一感覺是通過觀察樣例里的26，和前幾組數(shù)字；發(fā)現(xiàn)26的個(gè)數(shù)等價(jià)于2秒前4的個(gè)數(shù)，所以所有長度大于2的數(shù)都先回退到長度為1的基本情況然后去帶上減去的秒數(shù)，去算。
   比如26,9；等價(jià)于求4,7

image.png

多觀察這個(gè)圖很關(guān)鍵

這個(gè)做法在處理位數(shù)是2的CASE時(shí)候，發(fā)生了死循環(huán)；比如46-》66-》46成環(huán)了。
同時(shí)64-》42-》61-》44-》62-》41-》64 也是一個(gè)環(huán)

所以這個(gè)想法不WORK。在這里卡挺久的。
其實(shí)后來觀察到單獨(dú)針對2的CASE解出來，基本就拿到96分了。所以我的想法是對2位的數(shù)也建一個(gè)狀態(tài)機(jī)。
比如

16-> 26,64
64-> 64,41,16
42-> 16,64

這樣建變換矩陣的問題是會(huì)重復(fù)計(jì)算。
比如輸入是264；會(huì)變成41 1次，64 2次 ， 61 1次， 16 1次
但是正確答案是41 1次，64 1次 ， 61 1次， 16 1次
原因是6單個(gè)數(shù)字就可以擴(kuò)展成2位。所以在2位數(shù)的前一位是6和后一位是6生成的數(shù)字中會(huì)被重復(fù)計(jì)算。同時(shí)4也有這個(gè)問題。

然后想用容斥原理去解決掉重復(fù)計(jì)算的問題，比如4和6再最高位或最低位，直接不考慮。但是首字母和尾字母都可能會(huì)有4和6的情況。這樣會(huì)漏掉解。當(dāng)然如果是不用快速冪，而是線性迭代的話，這個(gè)問題是可以在遞推過程中修正掉的。但是10^9這里要求我們的遞推公式是不能有IF 的，必須是一個(gè)直接轉(zhuǎn)移。

最后通過把1位和2位的狀態(tài)結(jié)合在一起考慮列變換方程。發(fā)現(xiàn)可以不重不漏

5. 最后4分，寫完前面的，很快就可以發(fā)現(xiàn)3位的輸入，回溯到2位是沒有環(huán)的。大喜。然后提交跑了個(gè)TLE，因?yàn)榈谝话婊厮輰懛ㄊ潜┝厮荩f歸每一層只處理1個(gè)字母的回溯，枚舉每一個(gè)可能性隨后剪枝。
   通過進(jìn)一步觀察，我發(fā)現(xiàn)了一個(gè)性質(zhì)，這個(gè)回溯的過程，其實(shí)只有在首字母是可能出現(xiàn)分叉。
   比如4，是可以由上一位的2過來，也可以是上一位6得來。這個(gè)確定了之后，余下的都是唯一解。如果走不通必然就無解。
   所以就優(yōu)化了寫法，最后AC了。

6. 變換矩陣如果很大，可以用代碼生成，核心就是維護(hù)好A狀態(tài)可以變換到哪些B狀態(tài)。然后矩陣行代表FROM，矩陣列代表可以變換過去的TO，隨后 mat[from][to]++
   小伙伴可以拉上去看看S=1時(shí)的矩陣就理解了。

image.png

write then burn代碼，代碼格式和命名不太規(guī)范。有看不懂的可以在評論區(qū)留言

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main m = new Main();
        System.out.println(m.solve(sc.nextInt(), sc.next()));
    }
    int M = 998244353;
    int[] val2id = new int[67];
    int[] baseEle =   { 1,  2,     4,      6,     16,  26,  41,  42,  44,  46,  61,  62,  64,  66};
    int[][] convert = {{2},{4},{1,6,16},{6,4,64},{26},{46},{62},{64},{61},{66},{42},{44},{41},{46}};
    {
        Arrays.fill(val2id, -1);
        for (int i = 0; i < baseEle.length; i++) val2id[baseEle[i]] = i;
    }
    private int solve(int n, String s) {
        if (s.length() <= 2) return solveBase(val2id[Integer.parseInt(s)], n); // 96分
        else { // 4分
            int res = 0;
            for (int[] i : shorten(s, 0)) res = (res + solveBase(i[0], n - i[1])) % M;
            return res;
        }
    }
    
    private int solveBase(int id, int n) { // 矩陣快速冪
        int[][] init = new int[1][14]; init[0][0] = 1;
        int[][] mat = new int[14][14];
        for (int from  = 0; from < 14; from++) for (int to : convert[from]) mat[from][val2id[to]]++;
        while (n > 0) {
            if ((n & 1) == 1) init = mul(init, mat);
            mat = mul(mat, mat);
            n >>= 1;
        }
        return init[0][id];
    }

    private int[][] mul(int[][] a, int[][] b) { // 矩陣乘法
        int n = a.length, m = a[0].length, k = b[0].length;
        int[][] res = new int[n][k];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < k; j++)
                for (int q = 0; q < m; q++)
                    res[i][j] = (int) ((res[i][j] + (long) a[i][q] * b[q][j] % M) % M);
        return res;
    }

    int[] ones = {'4', 6, '6', 4}; // 2種忽略掉16的1，和64的6的特殊情況
    private List<int[]> shorten(String s, int dep) { // 回溯到上層；處理首字母，因?yàn)槭鬃帜缚赡苡?gt;1種情況
        if (s.length() <= 2) {
            int id = val2id[Integer.parseInt(s)];
            return id == -1 ? Collections.EMPTY_LIST : Arrays.asList(new int[]{id, dep});
        }
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < ones.length; i += 2)
            if (ones[i] == s.charAt(0)) res.addAll(shorten(ones[i+1] + postShorten(s, 1), dep + 1));
        res.addAll(shorten(postShorten(s, 0), dep + 1));
        return res;
    }
    String[] pos = {"2", "4", "/", "16", "/", "64"};
    private String postShorten(String s, int idx) { // 唯一可能性的回溯，找不到就返回一個(gè)非法字符代表無解
        StringBuilder sb = new StringBuilder();
        while (idx < s.length()) {
            int i = 0;
            for (; i < pos.length; i++) {
                if (s.startsWith(pos[i], idx) || (idx == s.length() - 1 && pos[i].charAt(0) == s.charAt(idx))) {
                    idx += pos[i].length();
                    sb.append(i + 1);
                    break;
                }
            }
            if (i == pos.length) return "0"; // invalid number
        }
        return sb.toString();
    }
}