P15220 [SWERC 2017] Macarons题解

· · 题解

My blog。

首先，因为本题的 n 非常小，我们可以考虑装压。

考虑目前有一个 x \times N 和一个 y \times N 的矩阵，我们可以将他们合并成一个 (x+y)\times N 的矩阵。这样一来，我们就需要知道每一个矩阵的第一行是什么样子、最后一行是什么样子。

定义 dp_{i,j,k} 表示一个 i \times N 的矩阵，第一行是 j 的样子，最后一行是 k 的样子（j 和 k 是装压）的方案数。为了方便转移，我们用 j 的二进制位中的 1 表示该位置已经被填， k 的二进制位中的 0 表示该位置已经被填。

我们尝试进行暴力转移：

for(int i=0;i<(1<<n);i++)
    for(int j=0;j<(1<<n);j++)
        for(int k=0;k<(1<<n);k++)
            dp[x+y][i][j]+=dp[x][i][k]*dp[y][j][k];

写出暴力转移方程后，我们惊奇的发现这与矩阵乘法的转移相似，遂可以用矩阵快速幂优化。

感觉这才是想出使用矩阵优化的思维路径。

时间复杂度 O(8^N \log M)。