ccf 202006

此算法模拟
https://blog.csdn.net/weixin_45919985/article/details/108101627
https://www.jianshu.com/p/efc9e984eff0
这两篇博客而写的，只用96分。
具体代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
//        long stime = System.currentTimeMillis();
        Scanner sc = new Scanner(System.in);
        Main m = new Main();
        System.out.println(m.bfs(sc.nextInt(), sc.next()));
//        long etime = System.currentTimeMillis();
//        System.out.println((etime - stime));
    }
    private long bfs(int n,String s){
        long ans = 0L;
        Queue q = new linkedList();
        q.offer(new Node(s,n));
        while (!q.isEmpty()){
            Node now = q.poll();
            if(now.s.length()==2||now.s.length()==1){
                ans = (ans+solve(now.s,now.n))%M;
            }else{
                String ts="";
                if((ts=backTrace(now.s))!="") //对于664这种情况会返回“”字符串（即回溯失败），做额外处理
                q.offer(new Node(ts,now.n-1));
                if(now.s.charAt(0)=='4' && (ts=backTrace("6"+now.s))!="") q.offer(new Node(ts,now.n-1));
                else if(now.s.charAt(0)=='6' && (ts=backTrace("1"+now.s))!="") q.offer(new Node(ts,now.n-1));
            }

        }
        return ans;
    }
    private String backTrace(String s){
        String rs = "";
        for(int i =0 ; i ids = new ArrayList(Arrays.asList("1", "2", "4", "6", "16","26","41","42","44","46","61","62","64","66"));
    private long solve(String s, int n){
        int[][] init = new int[1][14]; init[0][0] = 1;
        int[][] m = mat.clone();
        while (n > 0){
            if((n&1)==1) init = mul(init, m);
            m= mul(m,m);
            n>>=1;
        }
        return init[0][ids.indexOf(s)];
    }
    final int M = 998244353;

    private int[][] mul(int[][] init, int[][] m){
        int[][] rc = new int[init.length][m[0].length];
        for(int i =0; i