P8194

xujindong_ · 2025-10-30 18:29:32 · 题解

爆标做法。考虑把 DP 套 DP 直接扔掉，钦定当前状态按后 1/2/4 个分段，强行分讨去掉重复情况：

最后一个分段，f_i\gets f_i+f_{i-1}；

若 [i-1,i] 相邻，最后两个分段，要求这两个交换，否则被两个 1 段替代，f_i\gets f_i+f_{i-2}。

若 [i-3,i] 是正方形，最后四个分段，先让 f_i\gets f_i+24f_{i-4}，然后扣掉可以被替代的方案。

被 i 分一段的某个方案替代：

若 [i-3,i] 顺序是 1234，被四个 1 段替代，f_i\gets f_i-f_{i-4}。

若 [i-3,i] 顺序是 2314,3124,3214，这三种情况只可能被 [i-4,i-1] 分段的情况替代，若 [i-4,i-1] 是正方形则 f_i\gets f_i-3f_{i-5}。

若 [i-3,i] 顺序是 1324，若 [i-2,i-1] 相邻，此时可以钦定为按 i-3,[i-2,i-1] 分段。若 [i-4,i-1] 分段，能被 [i-4,i-3],[i-2,i-1] 替代。若按 [i-5,i-4] 分段，能被 i-5,i-4 替代；若按 [i-7,i-4] 分段，在 [i-7,i-5] 中必有两个相邻，可以 2+1 分段。因此可以转移 f_i\gets f_i-f_{i-4}，否则若 [i-5,i-1] 是正方形就转移 f_i\gets f_i-f_{i-5}。

若 [i-3,i] 顺序是 2134，若 i-3,i-2 相邻，钦定 [i-3,i-2],i-1,i 分段，[i-5,i-2] 分段的情况一定有 [i-5,i-4] 相邻，总是可以分成两段 2，因此已经被包含，转移 f_i\gets f_i-f_{i-4}。否则情况比较复杂：

如果能分段 [i-4,i-1]，就是 f_{i-4}。另一种方案是分段 i-1,i 且 [i-5,i-2] 的顺序是 2143（i-5,i-4 必须交换，否则被 [i-4,i-1] 分段的情况覆盖）。我们已知 [i-3,i-2] 在交错的位置，因此 [i-5,i-2] 必须能成段。注意，此时我们的前提条件是扣除 [i-3,i] 成段的方案数。

现在我们考虑 [i-3,i] 成段时 [i-7,i-4] 要成段，考虑 i-7,i-6 是否交换。若不交换，那这两个成段的限制已经满足，为 f_{i-8}。否则限制变为 [i-5,i-2],[i-7,i-4] 要能成段且 i-7,i-6 必须交换。发现这变成了一个子问题，我们可以拿一个 g_i 算出，为 g_i=\begin{cases}g_{i-2}+f_{i-4}&\ [i-3,i]\text{ is valid}\\0&\ \text{otherwise}\end{cases}。转移就是 f_i\gets f_i-g_{i-4}。

若 [i-4,i-1] 不能分段，就只有分段 i-1,i,[i-5,i-2]，比上面多一种 i-5,i-4 不交换的情况 f_{i-6}。转移是 f_i\gets f_i-f_{i-6}-g_{i-4}。

若被 [i-1,i] 分一段的某个方案替代（首先要求 i-1,i 相邻）：