Passage

Secret Passage 稍微观察一下就能发现，任一时刻，我们剩下的东西必然是一段定死了的后缀，加上一些可以任意塞位置的 0 与 1。考虑任意一个由上述时刻生成的串，就会发现它与该后缀的最长公共子序列长度即为后缀长度，且还剩余一些 0 与 1。 于是考虑模拟最长公共子序列的过程。设 \(g_{i ......

思路挺自然的一道 agc。 首先发现删除完字符后的状态可以用一个三元组 $(i,j,k)$ 表示，其中 $i$ 表示删除完之后只剩 $[i+1,n]$ 的后缀，$j$ 表示可以在后面插入 $j$ 个 $0$，$k$ 表示可以在后面插入 $k$ 个 $1$，显然不同的三元组能够得到的串是不同的，而一组 ......