2020.11.4笔记

发表于 2020-11-04 更新于 2020-11-05

【ZROI】联赛集训Day18

A

答案是 $cnt_{max}^n$。

串 $t$ 中每个字符 $c$ 的贡献为 $c$ 在 $s$ 中的出现次数，那必然要选贡献最高的那些才能卡到上界。

直接两个序列都升序排序即可，证明可以考虑不等式。

看起来有 $24$ 种情况，实际上可以只考虑 $1$ 在前两个位置的情况，剩下的情况都可以翻转得到，因此实际只需要考虑 $12$ 种情况。

除了 $3 1 4 2$ 需要用 $* 1 4 *$ 减掉 $2143$以外，剩余的情况都可以转化成枚举其中两个位置之后二维数点。

这个数据范围很小，可以二维前缀和预处理只有再做二维数点。

据说是$dp$套 $dp$ 然后发现状态只有 $123$ 种，因此可以矩阵快速幂优化，但是我不会写，咕了。