操作等价于选择一个子序列,再以某种方式填充满整个序列。
设 \(f_{i, a, b, c}\) 为子序列结尾为 \(j\) 此时 \(a, b, c\) 的数量分别为 \(a, b, c\) 时不同序列的方案数。
显然,我们需要从 \(s_i\) 不同的上一个 \(j\) 开始转移起,这样的 \(j\) 最多只有 \(3\) 种,由于 \(a, b, c\) 的上限都是 \(\frac{n}{3}\),所以复杂度是 \(O(\frac{n^4}{27})\),能够通过。
操作等价于选择一个子序列,再以某种方式填充满整个序列。
设 \(f_{i, a, b, c}\) 为子序列结尾为 \(j\) 此时 \(a, b, c\) 的数量分别为 \(a, b, c\) 时不同序列的方案数。
显然,我们需要从 \(s_i\) 不同的上一个 \(j\) 开始转移起,这样的 \(j\) 最多只有 \(3\) 种,由于 \(a, b, c\) 的上限都是 \(\frac{n}{3}\),所以复杂度是 \(O(\frac{n^4}{27})\),能够通过。