Solution：AT_fps_24_d 数列 2

· · 题解

与原题记号相同，令 A 为原数组，B 为排序后的数组。根据题目中的条件，显然 A 中的数必定两两不同，于是我们可以直接算 B 的方案数，最后乘上 N! 即可。

对于 B 的方案数，显然可以枚举差分数组 B'，这样限制就变成了 B_1' 任取，B_i'(i>1) 必须是奇数，且 B_i 的和不超过 M。于是答案就是

[x^M]\frac{1}{(1-x)^2}\left(\frac{x}{1-x^2}\right)^{N-1}

容易推式子或容斥做到 \Theta(n)。