壘骰子

?

賭圣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

---

題目分析：一看題目讓求方案數，肯定是一個動態規劃的題目跑不了了，再看一眼數據，最大能到1e9，那么肯定就要用矩陣快速冪優化了，先說一下如何用線性dp騙分吧，畢竟百分之60的數據的n最大才到100

首先設計dp數組，dp[i][j]代表的是截止到第i個骰子為止，第j面朝上時的方案數，對于這個題目，為了好處理對面關系，我們將所有的編號都減一，從1~6變為0~5，這樣一來就可以通過公式(x+3)%6求出編號x的對面了，然后初始化dp[1][j]=4，j=[0,5]，因為我們假設第一個骰子每一面朝上都有四種方案（旋轉），然后用一個二維數組maze保存一下哪些編號可以接觸，若編號i和編號j可以接觸，那么maze[i][j]=maze[j][i]=true，否則等于false，這樣就可以設計轉移方程了

if(maze[(j+3)%6][k])dp[i][j]+=dp[i-1][k]*4;

上面方程中的j代表的是第i個骰子朝上的面，k代表的是第i-1個骰子朝上的面，乘4是因為可以旋轉四次

這樣最后答案就是dp[n][i],i=[0,5]了

總的時間復雜度是n*6*6，大概能處理1e6的數據

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;const int mod=1e9+7;LL dp[N][6];bool maze[6][6];void init()//初始化 {for(int i=0;i<6;i++)for(int j=0;j<6;j++)maze[i][j]=true;//初始時所有的編號都是可以放置的memset(dp,0,sizeof(dp));for(int i=0;i<6;i++)//第一個骰子每個方向向上都有四種方法放置 dp[1][i]=4; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);init();int n,m;scanf("%d%d",&n,&m);while(m--){int x,y;scanf("%d%d",&x,&y);maze[x-1][y-1]=false;maze[y-1][x-1]=false;}for(int i=2;i<=n;i++)//從第二個骰子開始枚舉 for(int j=0;j<6;j++)//枚舉當前骰子朝下的一面 for(int k=0;k<6;k++)//枚舉上一個骰子朝上的一面 if(maze[j][k])dp[i][(j+3)%6]=(dp[i][(j+3)%6]+dp[i-1][k]*4)%mod;int ans=0;for(int i=0;i<6;i++)ans=(ans+dp[n][i])%mod;cout<<ans<<endl;return 0; }

但是，僅僅是這樣只能得到60%的分數，我們要追求100%的分數，就需要用到矩陣快速冪優化一下

其實看到上面的轉移方程，我們可以稍微轉換一下形式：

dp[i][j]+=maze[(j+3)%6][k]*dp[i-1][k]*4;

然后我們將所有的常數合并為M，那么上述方程就變成了：

dp[i][j]+=M*dp[i-1][k]，M=maze[(j+3)%6][k]*4;

這樣我們可以將常數M構造成一個6*6的矩陣，一開始的矩陣都初始化為4，按照題目構造好maze矩陣后直接套模板就可以實現了

時間復雜度為logn，可以處理1e9的數據了，甚至最多都能處理到1e18的數據

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=6;//構造6*6的矩陣const int mod=1e9+7;struct Ma {LL a[N][N];Ma(){memset(a,0,sizeof(a));}Ma operator*(const Ma& b)const{Ma ans;for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<N;k++)ans.a[i][j]=(ans.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;return ans;} };Ma q_pow(Ma a,LL b)//矩陣快速冪 {Ma ans;for(int i=0;i<N;i++)ans.a[i][i]=1;while(b){if(b&1)ans=ans*a;a=a*a;b>>=1;}return ans; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);Ma maze,ans;for(int i=0;i<N;i++)//初始化矩陣全部為4for(int j=0;j<N;j++)maze.a[i][j]=ans.a[i][j]=4;LL n;int m;scanf("%lld%d",&n,&m);while(m--)//構造矩陣{int x,y;scanf("%d%d",&x,&y);x--,y--;maze.a[(x+3)%6][y]=maze.a[y][(x+3)%6]=0;}ans=ans*q_pow(maze,n-1);LL sum=0;for(int i=0;i<N;i++)sum=(sum+ans.a[0][i]);cout<<sum<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的蓝桥杯 - 垒骰子(动态规划+矩阵快速幂优化)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。