Codeforces Round

vp。

D. Cut

尝试维护以 为左端点时同一段内最靠右的右端点 。

容易发现，随着 递增， 单调不降。可以双指针求。先筛出 以内所有数的质因数，这样就可以快速插入或删除一个数。

倍增统计答案即可。

E. Baby Ehab Plays with Permutations

不会。看 sol。

设 表示长度为 ，经过 次操作后第一次得到的排列数量。

考虑转移。当新加入一个数时，

• 放在排列最后，不需要交换。
• 不放在最后，需要 次交换。

注意可以浪费交换次数。答案 。

直接做复杂度是 的。考虑优化。

发现改变的位置至多只有 个。尝试从这里入手。

再设 表示长度为 ，经过 次操作且有 个位置不动的方案数。

容斥可得

最终答案即为