几道好欺负的杂题

larry76 / 2023-05-03 / 原文

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} \]

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

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

  1. 填了一个大于当前 \(\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\) 这一个维度,我们可以考虑滚动数组来优化我们的空间,否则应该会炸。