蓝桥垒骰子（dp+矩阵快速幂）

偏执的太偏执、 2022-05-29 12:46 191阅读 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

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

1.  思路：这道题可以用深搜，判断相邻的两个链接面是否冲突，但是数据量太大，所以这时候应该考虑一下是否可以用动态规划写，可以推出dp\[i\]\[j\] (代表第i层当j数字朝上的时候的个数) =  dp\[i-1\]\[k\] （1=<k<=6 && k与j的对面不冲突）的和。  但是这样依然不够 ，这样仍然需要 6e9的复杂度。
2.  所以要用构造矩阵（很难想到）构造方程如下

（fk1,fk2,fk3,fk4,fk5,fk6）\*(六行六列矩阵)=（f(k+1)1,f(k+1)2,f(k+1)3,f(k+1)4,f(k+1)5,f(k+1)6）;

矩阵第j列的的含义是当K+1层j朝上，第j列6个元素的意思意思是 k+1层j元素朝上的时候是否加上第K层i元素朝上的数量。

#include<cstdio>
    using namespace std;
    typedef long long ll;
    const ll mod=1e9+7;
    int opp[7]={0,4,5,6,1,2,3};//元素对对面
    bool compact[7][7];//冲突标记
    ll ans=0;
    
    struct Matrix{
    	ll m[7][7];
    };
    
    Matrix M_mul(Matrix a, Matrix b){
    	Matrix c;
    	
    	for(int i=1; i<=6; i++)
    	{
    		for(int j=1; j<=6; j++)
    		{
    			c.m[i][j]=0;
    			for(int k=1; k<=6; k++)
    			{
    				c.m[i][j]=(c.m[i][j]%mod+((a.m[i][k]%mod)*(b.m[k][j])%mod)%mod)%mod;
    			}
    		}
    	}
    	return c;
    }
    
    Matrix M_pow(Matrix a, int t){
    	Matrix ans;
    	for(int i=1; i<=6; i++)
    		for(int j=1; j<=6; j++)
    			if(i==j) ans.m[i][j]=1;
    			else	ans.m[i][j]=0;			
    	
    	while(t){
    		
    		if(t&1){
    			ans=M_mul(ans, a);
    		}
    		a=M_mul(a,a);
    		t>>=1;
    	}
    	return ans;
    }
    
    int main(){
    	Matrix compose;
    	int n, m;
    	scanf("%d%d", &n, &m);
    	for(int i=1; i<=6; i++)
    		for(int j=1; j<=6; j++)
    			compact[i][j]=false;
    		
    	for(int i=1; i<=m; i++)
    	{
    		int u, v;
    		scanf("%d%d", &u, &v);
    		compact[u][v]=true;
    		compact[v][u]=true;
    	}
    	
    	for(int i=1; i<=6; i++)//构造矩阵，如果可以为4因为可以旋转，否则为0.
    	{
    		for(int j=1; j<=6; j++)
    		{
    			if(compact[j][opp[i]])
    				compose.m[j][i]=0;
    			else
    				compose.m[j][i]=4;
    		}
    	}
    	
    	compose=M_pow(compose, n-1);
    	for(int i=1; i<=6; i++)
    	{
    		for(int k=1; k<=6; k++)
    		{
    			ans=(ans%mod+4*compose.m[k][i]%mod)%mod;//乘4的意思是一层的时候每一个面朝上都有四种情况。
    		}
    	}
    	
    	printf("%lld\n", ans);
    	return 0;
    }