警惕洛谷题解同质化问题

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_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)$，跑进了时限的一半。

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