警惕洛谷题解同质化问题

NewMarchqwq · 2025-08-29 12:47:54 · 题解

1-indexed

咋题解都是推式子，给一个整体 dp 做法，这个做法连模数是质数都不需要保证。

把题目中条件翻译成人话就是重排后的 a 序列得满足 \forall 2\le i\le n,|a_i-\max\{a_1,a_2,\dots,a_{i-1}\}|>k。那么我们遇到这种排列问题第一眼肯定想想按照一个顺序加数。我们不妨从大到小加数。这样有一个好处：如果这样加了一个数导致序列不合法，那么他一定到最后都不合法了，因为加的那个数前面的 max 不会变了。

考虑你比现在这个数 x 大的所有数都加进了序列 w（设 w 的大小 >1，否则是平凡的）。那么我们考虑分类讨论：

• 当 w_1-x>d 的时候，你显然把 x 加哪里都行；
• 当 w_1-x\le d 时，一定有 w_2\ge w_1。因为如果 w_2<w_1，我们又 x\le w_2，就是 w_1-w_2\le d 也成立，显然这是不行的。因此我们一定能够把 x 插 w_2 后面、w_3 后面等等。

因此注意到我们不需要知道 w_2 等的值只需要知道 w_1。考虑 dp：f(i,j) 表示填好了 i\sim n，这时 w_1=a_j。我们有转移（注意把 a_i=x 放最前面的情况单独算）：

答案即为 \sum_i f(1,i)。这样做到了平方。

优化是显然的整体 dp。发现你只需要一个区间乘，单点修，区间求和的线段树即可维护上面的转移。复杂度 \Theta(n\log n)，跑进了时限的一半。

马上加强到对小合数取模，阶乘哥们受死吧。