[Acwing|蓝桥] 1217. 垒骰子 dp求方案数+矩阵乘法

前言

传送门 :

题意

有多个骰子,竖成一列的队列,规定 a i b i a_ib_i ai​bi​表示如果 a i a_i ai​是下面那个骰子的顶,那么 b i b_i bi​就不能是上面那个骰子的底。反之亦然,求合法方案数

这里的骰子 1的对面不是6注意,题面有明确规定

思路

首先常规做法考虑 d p dp dp : 状态表示 f [ i ] [ j ] : f[i][j] : f[i][j]:从前 i i i个骰子选且第 i i i个骰子数字 j j j朝上的所有方案数

状态转移 f [ i ] [ j ] = f [ i − 1 ] [ k ] ∗ 4 ( s t [ k ] [ o p [ j ] ] ! = 0 ) f[i][j] =f[i-1][k] * 4(st[k][op[j]]! =0) f[i][j]=f[i−1][k]∗4(st[k][op[j]]!=0) ( s t [ k ] [ j ] st[k][j] st[k][j]表示两个数字是否互斥

这里讲的 o p op op表示对面的数字,因为当你枚举到第 i i i层的时候,判断矛盾是 i i i 和 i − 1 i-1 i−1层进行判断,所以也需要知道当前以 j j j为顶的对面的数字

显然这是会超时的,因为数据范围 1 e 9 1e9 1e9

因此我们考虑使用矩阵乘法进行优化 :

令 F ( n ) = [ f [ n ] [ 1 ] , f [ n ] [ 2 ] , f [ n ] [ 3 ] , f [ n ] [ 4 ] , f [ n ] [ 5 ] , f [ n ] [ 6 ] ] F(n) = [f[n][1],f[n][2],f[n][3],f[n][4],f[n][5],f[n][6]] F(n)=[f[n][1],f[n][2],f[n][3],f[n][4],f[n][5],f[n][6]] 则 F ( n + 1 ) = [ f [ n + 1 ] [ 1 ] , f [ n + 1 ] [ 2 ] , f [ n + 1 ] [ 3 ] , f [ n + 1 ] [ 4 ] , f [ n + 1 ] [ 5 ] , f [ n + 1 ] [ 6 ] ] F(n+1) = [f[n+1][1],f[n+1][2],f[n+1][3],f[n+1][4],f[n+1][5],f[n+1][6]] F(n+1)=[f[n+1][1],f[n+1][2],f[n+1][3],f[n+1][4],f[n+1][5],f[n+1][6]]

考虑 F ( n ) ∗ A [ 6 ] [ 6 ] = F ( n + 1 ) F(n)*A[6][6] = F(n+1) F(n)∗A[6][6]=F(n+1)

F ( n ) [ 4 0 4 4 0 4 4 4 0 0 4 4 0 4 4 4 4 4 4 4 4 4 4 0 4 0 4 0 4 4 4 4 4 4 0 4 ] = F ( n + 1 ) ( 条 件 : [ 1 2 1 5 2 6 3 4 5 5 ] ) 当 前 行 与 当 前 列 互 斥 F(n)\begin{bmatrix} 4&0&4&4&0&4\\ 4&4&0&0&4&4\\ 0&4&4&4&4&4\\ 4&4&4&4&4&0\\ 4&0&4&0&4&4\\ 4&4&4&4&0&4\\ \end{bmatrix}=F(n+1)(条件 :\begin{bmatrix} 1&2\\ 1&5\\ 2&6\\ 3&4\\ 5&5 \end{bmatrix})当前行与当前列互斥 F(n)⎣⎢⎢⎢⎢⎢⎢⎡​440444​044404​404444​404404​044440​444044​⎦⎥⎥⎥⎥⎥⎥⎤​=F(n+1)(条件:⎣⎢⎢⎢⎢⎡​11235​25645​⎦⎥⎥⎥⎥⎤​)当前行与当前列互斥 (数据借 : 蔗)

观察发现,只有互斥的时候, A i j = 0 A_{ij} = 0 Aij​=0 F n = F 0 ∗ A n = F 1 ∗ A n − 1 F_n = F_0*A^n=F_1*A^{n-1} Fn​=F0​∗An=F1​∗An−1 所以我们就构造出了, A A A,下面就可以愉快的进行 d p dp dp了

Mycode

const int N  = 6 ,mod = 1e9+7;



int op[N] = {3,4,5,0,1,2};
int n,m;
int A[N][N];

void mul(int c[][N],int a[][N],int b[][N]){
	int  t[N][N] = {0};
	
	for(int i=0;i>m;
	
	for(int i=0;i>b;
		a--,b--;
		A[a][op[b]] = 0;
		A[b][op[a]] = 0;
	}
	
	int f1[N][N] = {4,4,4,4,4,4};
	//表示只有一共骰子的时候 那么肯定就是 4 了


    
	for(int k = n-1;k;k>>=1){
		if(k&1) mul(f1,f1,A);//F =  F*A;
		mul(A,A,A);// A = A*A
	}


	int res = 0;
	for(int i = 0;i