1.dfs七个点

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n;
    static int[] bit = new int[7];//用来存储每个数和哪个数互斥
    static long res;
    static long mod = 1000000007;
    static int[] back = {0,4,5,6,1,2,3};
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        int m = input.nextInt();
        for (int i = 0; i < m; i++) {
            int a = input.nextInt();
            int b = input.nextInt();
            bit[a] |= (1 << b);
            bit[b] |= (1 << a);
        }
        //System.out.println(Arrays.toString(bit));
        //bit存放了互斥关系
        for(int i = 1 ; i <= 6 ; i++) {
            dfs(1,4,i);
        }
        System.out.println(res);
    }
    private static void dfs(int i,long curCnt, int up) {
        //当前已经枚举了i个骰子、方案数为curCnt，当前顶上为up
        if(i == n) {
            res = (res + curCnt) % mod;return;
        }
        for(int k = 1 ; k <= 6 ; k++) {
            //看看下一个能不能放k
            if(((bit[up] >> k) & 1) == 0) {
                //可以放
                dfs(i+1, curCnt * 4 % mod, back[k]);
            }
        }
    }
}

2普通dp7个点、不优化空间，第7个点报OOM，否则报TTL

2.1不优化空间

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[] back = {0,4,5,6,1,2,3};
    static long mod = 1000000007;
    public static void main(String[] args) {
        //dp[i][j] 是有i个筛子，最上面一个筛子是j的合法方案的数量
        //初始化dp[0][j]都为1
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        long[][] dp = new long[n+1][7];
        int[] bit = new int[7];
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            bit[a] |= (1 << b);
            bit[b] |= (1 << a);
        }
        for(int i = 1 ; i<= 6 ; i++)dp[1][i] = 4;
        for(int i = 2 ; i <= n ; i++) {
            for (int j = 1; j <= 6; j++) {
                //dp[i][j] j的背面是back[j],看看i-1中和back[j]不互斥的有哪些方案
                int bk = back[j];
                for(int k = 1 ; k <= 6 ; k++) {
                    if(((bit[bk] >> k) & 1) == 0) {
                        dp[i][j] = (dp[i][j] + 4 * dp[i-1][k]) % mod;
                    }
                }
            }
        }
        long res = 0;
        for(int i = 1 ; i<= 6 ; i++) {
            res = (res + dp[n][i]) % mod;
        }
        System.out.println(res);
    }
}

2.2优化空间

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[] back = {0,4,5,6,1,2,3};
    static long mod = 1000000007;
    public static void main(String[] args) {
        //dp[i][j] 是有i个筛子，最上面一个筛子是j的合法方案的数量
        //初始化dp[0][j]都为1
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
//      long[][] dp = new long[n+1][7];
        long[] dp = new long[7];
        int[] bit = new int[7];
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            bit[a] |= (1 << b);
            bit[b] |= (1 << a);
        }
        for(int i = 1 ; i<= 6 ; i++)dp[i] = 4;

        for(int i = 2 ; i <= n ; i++) {
            long[] cur = new long[7];
            for (int j = 1; j <= 6; j++) {
                //dp[i][j] j的背面是back[j],看看i-1中和back[j]不互斥的有哪些方案
                int bk = back[j];

                for(int k = 1 ; k <= 6 ; k++) {
                    if(((bit[bk] >> k) & 1) == 0) {
                        cur[j] = (cur[j] + dp[k] * 4) % mod;
                    }
                }

            }
            dp = cur;
        }
        long res = 0;
        for(int i = 1 ; i<= 6 ; i++) {
            res = (res + dp[i]) % mod;
        }
        System.out.println(res);
    }
}

3.矩阵快速幂，写完普通dp后根据递推关系，推出关系矩阵求n个筛子要乘以n-1次矩阵，所以用矩阵快速幂

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[] back = {3,4,5,0,1,2};
    static long mod = 1000000007;
    static long[][] matrix = new long[6][6];
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        int[] bit = new int[6];
        for(int i = 0 ; i < m ; i++) {
            int a = input.nextInt() - 1;
            int b = input.nextInt() - 1;
            bit[a] |= (1 << b);
            bit[b] |= (1 << a);
        }

        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                int bk = back[j];
                if(((bit[bk] >> i) & 1) == 0) {
                    matrix[i][j] = 4;
                }
            }
        }
//      for (int i = 0; i < bit.length; i++) {
//          System.out.println(Arrays.toString(matrix[i]));
//      }
        if(n == 1) {
            System.out.println(24);
        }else {
            long[][] ma = cal(n-1);
            long[][] start = new long[][]{{4,4,4,4,4,4}};
            long[][] resMatrix = multi(start,ma);
            long res = 0;
            for(int i = 0 ; i < 6 ; i++) {
                res = (res + resMatrix[0][i]) % mod;
            }
            System.out.println(res);

        }
    }
    private static long[][] cal(int n) {
        long[][] res = {
                {1,0,0,0,0,0},
                {0,1,0,0,0,0},
                {0,0,1,0,0,0},
                {0,0,0,1,0,0},
                {0,0,0,0,1,0},
                {0,0,0,0,0,1}};

        while(n > 0) {
            if((n & 1) == 1) {
                res = multi(res,matrix);
            }
            n = n >> 1;
            matrix = multi(matrix,matrix);
        }
        return res;
    }
    private static long[][] multi(long[][] m1, long[][] m2) {
        long[][] res = new long[m1.length][m2[0].length];
        for(int i = 0 ; i < m1.length ;i++) {
            for(int j = 0 ; j < m2[0].length ; j++) {
                for(int k = 0 ; k < m1[0].length ; k++) {
                    res[i][j] = (res[i][j] + m1[i][k] * m2[k][j]) % mod; 
                }
            }
        }
        return res;
    }
}