今天依旧睡到 7 点半???，爽！
上午不知道干了啥，好像无所事事了一上午。好像是把 zzz 讲的构造思维题写了写，好像还写了道据说很卡常的题，但是没卡常就过了，说不定是我代码里出现了 Genshin_Impact 把评测机逼急了所以跑的快了捏???
中午和 wyy 聊到一点准备回去睡觉发现 lbx 把屋门锁上了?，为了不打扰 lbx 睡觉我只能接着和 wyy 聊到 lbx 起床了???。下午还被 lbx D说回来太晚了???
下午好像也无所事事了一下午，把 lyt 之前讲课的课件的题写了写，发现都不会?，迟早退役哈哈。
我草怎么感觉我这么摆啊
一些牢骚：说实话有的时候真的没法理解某谷上面为什么会他妈的出来那么多什么网红，天天想着涨粉。真搞不懂涨粉有啥意义，某谷不就是用来做题和交流的吗怎么搞的和饭圈一样?。有的网红也是差不多得了顶个绿勾天天灌水帖子能见着学术帖子见不着，还有某些人顶个金钩红名天天攻击性那么强也不去学术帖子下回复整天就会个 wyy，jbl 是吧???。真想当网红去别的平台，不要在某谷当个网红来显示你在别的地方啥粉丝都吸引不了只能在某谷发发言的无能了???
@lelekue 说句实话，我发现您有贺题解的情况，但是你以为我会举报吗，我当然不会
写完上面这段话挺生气的，但是生气又碍不着它们一点事情，倒还不如劝劝看到这里的你把 exlg 的犇犇排行榜和全网犇犇关掉，过滤一堆傻逼（如果你没下 exlg 或者已经关了当我没说）
推歌：Nyarlathotep's Dreamland -Raimukun
Lanota 的书房魔王曲，钢琴很好听，反正第一次听到的时候就被震撼到了。看到谱面说实话也被震撼到了，总之就是很好听。
P4590
本题感觉有意思。
我们首先可以把不形成 NOI 的限制扔掉，因为我们转移的时候一定是枚举填这三个字母中的一个，在状态里多加一维来记录匹配上第几位即可。
我们先回忆一下最长上升子序列的转移方程：
设 \(f_{a, b}\) 为考虑未知的串（下面用 \(\mathrm{A}\) 表示）的前 \(a\) 位，原串（用 \(\mathrm{B}\) 表示）前 \(b\) 位的最长公共子序列
我们考虑在串后面加入一个新字符，就会对这个状态产生一定的影响。这启发我们可以对这个状态建立一个自动机。其中自动机中的边就代表着填入什么字符，自动机中的节点就代表着我们固定 \(a\) 后 \(f_{a, i}\) 中的 \(|\mathrm{B}|\) 个数。这样我们添加一个字符后就能通过上面的转移方程快速的求出新到的节点为哪一个。
具体的说，我们设 \(F_{i, j}\) 表示考虑 \(\mathrm{A}\) 的前 \(i\) 位，当前在自动机中的第 \(j\) 个节点时的方案数。转移就枚举新加入的字符，然后用转移方程计算新到的节点即可。
但是我们现在又有一个问题：自动机的节点可能会达到 \(15^15\) 级别，我们的状态存不下。但是我们思考这些状态能有什么特点：相邻两位相差不超过 \(1\)。利用这个性质我们就可以差分一下，把一个 \(f_{a, i}\) 压缩成一个 \(15\) 位的二进制数，这样就存的下来了。
时间复杂度 \(O(2^kk|\mathrm{A}|)\)
