CF1349F2 Slime and Sequences

· · 题解

其他的别的题解讲的很清楚了，我来讲讲怎么想到这个双射。

我们发现题目的限制相当于 i 的第一次出现 <i+1 的最后一次出现。

此时还是没有什么头绪，不妨考虑把他写出来看需要满足什么。

我们把每个数 i 的第一次出现位置记为 L_i ，最后一次出现记为 R_i 。

把它按这样接起来，发现了他们之间全都是 < 。

出现位置，小于号，你想到了什么？

没错，把 R,L 之间 i 的每次出现位置都补齐，那么他就是一个有 i-1 个小于号的排列的数量，直接欧拉数解决。