题解：P8624 [蓝桥杯 2015 省 AB] 垒骰子

_O_v_O_ · 2024-05-31 22:50:56 · 题解

设 dp_{i,j} 为第 i 个骰子向上的面为 j 的方案数。

那么 dp_{i,j}=\sum_{k=1}^6 dp_{i-1,k}[(j+3)\bmod 3,k\text{不互斥}]。

这是 O(n) 的，考虑矩阵优化。

我们只用注意转移矩阵 base，很明显，我们只用把刚才的转移具体成矩阵即可，具体的，初始所有的都为 4，然后每有一组关系 (i,j) 就将矩阵中对应位置置为 0。

然后这题就可以解了。