蓝桥杯2015初赛 垒骰子 DP动规 题解

蓝桥杯2015初赛 垒骰子 DP动规+矩阵快速幂 题解

首先简化题目描述：共有 n n n个骰子，骰子的组成规则遵循(14)、(25)、(36)，现在将骰子落成一个竖条，必须满足 m m m个条件：条件要求每组的两个骰子标号互斥而不能面对面摞在一起。

容易想到枚举每个骰子某面向上的状态，通过 m a p map map打标记检查状态是否合法，不合法的回溯。

但是一看数据范围，枚举显然行不通，于是考虑动态规划。

走经典的 D P DP DP分析法：

1.状态表示：首先确定发生转移的状态：骰子的序号(第 i i i个骰子)、每个骰子向上的面的点数 j j j(根据面向上的点数可以推出向下的点数，因此视为同一个状态)。当确定上下面之后，对于每个骰子而言，四个面的朝向均具有 4 4 4种不同的方案，因此可以单独计算状态。

那么我们可以用 d p [ i ] [ j ] dp[i][j] dp[i][j]表示高度为 i i i，顶面点数为 j j j的方案数。

2.最后一次状态转移： d p [ i ] [ j ] dp[i][j] dp[i][j]由 d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i−1][j]转移而来，即i-1 高度时所有与j的反面无冲突的方案数累加

3.状态转移方程： d p [ i ] [ j ] = ∑ j 6 d p [ i − 1 ] [ j ]     （ j ′ s   o p p o s i t e   − >   n o   c o n f l i c t   w i t h   i ） dp[i][j]= \sum_j^6dp[i-1][j] \ \ \ （j's \ opposite \ -> \ no \ conflict \ with \ i） dp[i][j]=j∑6​dp[i−1][j]   （j′s opposite −> no conflict with i） 可以采用滚动数组优化 d p dp dp转移方程，即设置两层相互滚动。那么可以写出程序代码：

#include 
#define ll long long
using namespace std;

const int opst[7] = {0, 4, 5, 6, 1, 2, 3};
const int mod = 1e9 + 7;
int conf[7][7], dp[2][7];

inline ll quick_pow(int x, int y){
    ll ans = 1;
    while(y > 0){
        if(y & 1) ans = (ans * x) % mod;
        y >>= 1;
        x = (x * x) % mod;
    }
    return ans;
}

signed main(){
    int n, m; cin >> n >> m;
    for(register int i = 0; i > a >> b;
        conf[a][b] = 1, conf[b][a] = 1;
    }
    for(register int i = 1; i > b;
            ma.m[opst[a] - 1][b - 1] = 0;
            ma.m[opst[b] - 1][a - 1] = 0;
        }
        matrix mb = mb.qmi(ma, n - 1);
        ll t = 0;
        for(int i  = 0; i