几道好欺负的杂题

标签：cdot text 转移 几道 欺负 mathcal 杂题 MEX dp

P7325 [WC2021] 斐波那契

会同余 + set 可以解决改题。

CF1264D1 Beautiful Bracket Sequence (easy version)

性质题，找到性质后就不会很难了

CF1264D2 Beautiful Bracket Sequence (hard version)

上一道题的强化版，如果你会范德蒙德卷积就很简单了，否则需要考虑组合意义来优化 dp。

CF1608F MEX counting

好前三道题是因为写了题解了就不多说了，这里把这道题的题解写一写。

分析题目，发现题目的意思是想让我们的 \(\text{MEX}\) 处在一个范围 \([l,r]\) 之内。

首先最朴素的 dp 状态还是比较套路的，就是设 \(dp_{i,j,k}\) 为已经处理到了 \(i\) 个数，此时的 \(\text{MEX}\) 为 \(k\)，且比它大的有 \(j\) 个不同的数的方案数有多少。我们首先不难想到将转移分为两大类，分别是接下来填的数不是 \(\text{MEX}\) 和接下来填的数是 \(\text{MEX}\) 这两类。

考虑接下来填的数不是 \(\text{MEX}\) 怎么转移，我们可以发现有三类转移：

1. 填了一个小于当前 \(\text{MEX}\) 的数字：

\[dp_{i,j,k} \to dp_{i+1,j,k} \]

2. 填了一个大于当前 \(\text{MEX}\) 且之前出现过的数字：

\[j \cdot dp_{i,j,k} \to dp_{i+1,j,k} \]

3. 填了一个大于当前 \(\text{MEX}\) 且之前没出现过的数字：

\[dp_{i,j,k} \to dp_{i+1,j+1,k} \]

考虑接下来填的数字是 \(\text{MEX}\) 该怎么转移，显然有废话 “如果 \(\text{MEX}\) 的值发生改变，则新改变的值一定大于原先的值”，所以考虑枚举新的 \(\text{MEX}\) 转移，设新的 \(\text{MEX}\) 为 \(t\)，于是有：

\[A^{j}_{t-k-1} \cdot dp_{i,j,k} \to dp_{i+1,j-(t-k-1),t} \]

此时，我们不难看出我们的时间复杂度为 \(\mathcal O (n^4)\)，空间复杂度为 \(\mathcal O(n^3)\)，无法通过此题。

考虑如何优化，首先我们可以发现在进行接下来填的数字是 \(\text{MEX}\)的转移时，有很多转移是没有必要的，事实上我们只需要转移 \(k\) 次就好，因为当我们的 \(\text{MEX}\) 大于 \(k\) 的时候是显然没有意义的，此时时间复杂度被优化到 \(\mathcal O(n^2 k^2)\)，依旧无法通过此题。

我们仔细观察最后一种转移，发现其本质就是做了一次相邻的斜着的转移，所以完全可以做前缀和，但是发现如果这样搞前缀和是一个斜着的情况，所以我们可以给第二个状态 \(+k\) 将斜着的转移拉直，考虑这样之后的转移的变化：

\[j \cdot dp_{i,j,k} \to dp_{i+1,j,k} \]

\[dp_{i,j,k} \to dp_{i+1,j+1,k} \]

\[\frac{(j-k)!}{(j-1-t)!} \cdot dp_{i,j,k} \to dp_{i+1,j+1,t} \]

时间复杂度被我们优化至 \(\mathcal O(n^2k)\)，可以通过本题，实际上还需要一点点的卡常技巧。

对于 \(i\) 这一个维度，我们可以考虑滚动数组来优化我们的空间，否则应该会炸。

标签：cdot,text,转移,几道,欺负,mathcal,杂题,MEX,dp
From： https://www.cnblogs.com/larry76/p/17367809.html