Affinity for Artifacts

Chasing_Meteors · 2025-12-02 10:49:09 · 题解

题目所求为一个集合 S=\{p\}。其中 p 是一个 1\sim n 的排列，我们先让 a_i\gets a_{p_i}。

题述限制等价于 (\sum \max(a_i-i+1,0))，\max 不好，因为取值太大了，改为 (\sum a_i-i+1-\min(a_i-i+1,0))\le X。

注意到 a_i\ge n-1 的没有考虑的意义，因为满足此的话，一定会使得贡献非负。

处理出来常数项，记 x=\sum a_i+1。

继续观察我们发现，我们不妨计算 y=\sum \min(a_i+1,i)，因为 y\le \frac{n\times(n+1)}{2}。

此时限制就是 x-X\le y。

我们考虑通过单调递增的序列来生成 a，因为这样无需考虑某个值的每个数填在哪里。另一种理解方式是从下标来考虑，同时将对 y 的贡献前置。

设 f(i,j,k) 表示处理到值为 i 元素，放置了 j 个元素，y 为 k 且单调上升的 \prod (j-i+1) 的和。

枚举选了几个 i 转移即可。

注意到有可能第 i 个位置上填了更大的数，然后占用了一个位置，所以也要转移这种方案，然后就好了。