蓝桥杯垒骰子（DP or 矩阵）（JAVA）

╰+攻爆jí腚メ 2023-07-13 15:02 100阅读 0赞

### 垒骰子 ###

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。  
经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！  
我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。  
假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。 atm想计算一下有多少种不同的可能的垒骰子方式。  
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。  
由于方案数可能过多，请输出模 10^9 + 7 的结果。

不要小看了 atm 的骰子数量哦～

##### 「输入格式」 #####

第一行两个整数 n m  
n表示骰子数目  
接下来 m 行，每行两个整数 a b ，表示 a 和 b 不能紧贴在一起。

##### 「输出格式」 #####

一行一个数，表示答案模 10^9 + 7 的结果。

##### 「样例输入」 #####

2 1  
1 2

##### 「样例输出」 #####

544

##### 「数据范围」 #####

对于 30% 的数据：n <= 5  
对于 60% 的数据：n <= 100  
对于 100% 的数据：0 < n <= 10^9, m <= 36

资源约定：  
峰值内存消耗（含虚拟机） < 256M  
CPU消耗 < 2000ms

#### 分析： ####

有n层骰子，每层每个面朝上均对应着4种情况，所以先把4的n次方抽离出来

#### DP解法【75%分数】 ####

DP就是进行递推  
以题中例子举例

当n=1时，骰子可以随意摆放  
即  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]  
当n=2时，第一层所有的不与当前值对立面所排斥的值的和即为该位置的值，  
第二层且1朝上时，4在他的对立面，，4不与任何值排斥，即为1+1+1+1+1+1  
第二层且2朝上时，5在他的对立面，，4不与任何值排斥，即为1+1+1+1+1+1  
第二层且3朝上时，6在他的对立面，，4不与任何值排斥，即为1+1+1+1+1+1  
第二层且4朝上时，1在他的对立面，，1与2排斥，即为1+0+1+1+1+1  
第二层且5朝上时，2在他的对立面，，2与1排斥，即为0+1+1+1+1+1  
第二层且6朝上时，3在他的对立面，，4不与任何值排斥，即为1+1+1+1+1+1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]  
对第二层求和得到34，  
34乘以4的n次方即为解。

#### 时间复杂度O（n）超时 ####

#### DP代码： ####

package JB2015;
    
    import java.util.Arrays;
    import java.util.Scanner;
    //DP只能拿60%分数
    public class I垒骰子DP { 
    	public static int dp[][] = new int[2][7];
    	public static boolean paichi[][] = new boolean[7][7];
    	public static int op[] = {  0, 4, 5, 6, 1, 2, 3 };
    	public static int MOD = 1_000_000_007;
    
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt(), m = sc.nextInt();
    		for (int i = 0; i < m; i++) { 
    			int x = sc.nextInt();
    			int y = sc.nextInt();
    			paichi[x][y] = true;
    			paichi[y][x] = true;
    		}
    		for (int i = 0; i < 7; i++) { 
    			dp[0][i] = 1;
    		}
    		int cur = 0;
    		for (int i = 1; i < n; i++) { 
    			cur = (cur + 1) % 2;
    			for (int j = 1; j < 7; j++) { 
    				dp[cur][j] = 0;
    				for (int k = 1; k < 7; k++) { 
    					if (paichi[j][op[k]]) { 
    						continue;
    					} else { 
    						dp[cur][j] += dp[(cur + 1) % 2][k];
    						dp[cur][j] %= MOD;
    					}
    				}
    			}
    			System.out.println(Arrays.toString(dp[cur])+" "+i);
    		}
    		int ans = 0;
    		for (int i = 1; i < 7; i++) { 
    			ans += dp[cur][i];
    			ans %= MOD;
    		}
    		long b = 4;
    		for (int i = 1; i < n; i++) { 
    			b *= 4;
    			b %= MOD;
    		}
    		System.out.println((ans * b) % MOD);
    	}
    }

#### 矩阵解法【满分】 ####

##### 时间复杂度（logn） #####

依旧以题中样例进行图解  
初始化第一层  
![在这里插入图片描述][20200313214527849.png]

我们采用矩阵的乘法，使我们用已知矩阵乘排斥矩阵得到下一层矩阵  
即  
Ps：与矩阵乘法不同的是我们用值的对立面去乘  
左边矩阵第一个值乘中间矩阵第四列  
左边矩阵第二个值乘中间矩阵第五列  
左边矩阵第三个值乘中间矩阵第六列  
左边矩阵第四个值乘中间矩阵第一列  
左边矩阵第五个值乘中间矩阵第二列  
左边矩阵第六个值乘中间矩阵第三列

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]  
ans=（6+6+6+5+5+6）\*4^n;

#### 推论 ####

我们可以每乘一个排斥矩阵得到下一层，即  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]

#### n-1个矩阵的乘积可以采用矩阵运算的快速幂 ####

#### 矩阵AC代码 ####

package JB2015;
    
    import java.util.Scanner;
    //满分
    public class I垒骰子矩阵 { 
    	public static long paichi[][][] = new long[32][7][7];
    	public static int op[] = {  0, 4, 5, 6, 1, 2, 3 };
    	public static int MOD = 1_000_000_007;
    //矩阵相乘
    	public static long[][] pow(int x, int y) { 
    		long ans[][] = new long[7][7];
    		for (int i = 1; i < 7; i++) { 
    			for (int j = 1; j < 7; j++) { 
    				for (int k = 1; k < 7; k++) { 
    					ans[i][j] += (paichi[x][i][k] * paichi[y][k][j]);
    					ans[i][j] %= MOD;
    				}
    			}
    		}
    		return ans;
    	}
    //求数字快速幂
    	public static long ksm(long x, long y) { 
    		long res = 1;
    		while (y > 0) { 
    			if (y % 2 > 0)
    				res = (res * x) % MOD;
    			x = (x * x) % MOD;
    			y >>= 1;
    		}
    		return res;
    	}
    
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt(), m = sc.nextInt();
    		for (int i = 1; i < 7; i++) { 
    			for (int j = 1; j < 7; j++) { 
    				paichi[0][i][j] = 1;
    			}
    		}
    		for (int i = 0; i < m; i++) { 
    			int x = sc.nextInt(), y = sc.nextInt();
    			paichi[0][op[x]][y] = 0;
    			paichi[0][op[y]][x] = 0;
    		}
    		//初始化2^n各个矩阵
    		for (int i = 1; i < 32; i++) { 
    			paichi[i] = pow(i - 1, i - 1);
    		}
    		//初始化答案矩阵
    		for (int i = 1; i < 7; i++)
    			for (int j = 0; j < 7; j++)
    				paichi[31][i][j] = (i == j) ? 1 : 0;
    		//求矩阵快速幂
    		int count = n - 1;
    		for (int i = 30; i >= 0; i--) { 
    			if (count >= (long) (Math.pow(2, i) + 0.01)) { 
    				paichi[31] = pow(31, i);
    				count -= (long) (Math.pow(2, i) + 0.01);
    			}
    		}
    		//计算所有情况总和ans
    		long ans = 0;
    		for (int i = 0; i < 7; i++) { 
    			for (int j = 0; j < 7; j++) { 
    				ans += paichi[31][i][j];
    				ans %= MOD;
    			}
    		}
    		System.out.println((ans * ksm(4, n)) % MOD);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20230529/eaea6b9fd4e64aa8b7c95cb520d9aa9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: /images/20230529/062b705eedb74e11b18d40c62b473ef2.png
[20200313214527849.png]: /images/20230529/da42b58da3ee43a18fba2af36a0ebc56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: /images/20230529/44c0e8bdb42e4340bc006d41c17a4353.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]: /images/20230529/29bef38cbdab4f67850bd5c86109d7dc.png