题意

求所有 $n$ 的排列的逆序对数的 $m$ 次方的期望，模 $998244353$。$n\le 10^{18},m\le 10^3$

题解

显然 $n\ge 998244353$ 的时候答案为 $0$

考虑从左往右依次加入排列的每一位

设加入第 $i$ 位以后的逆序对数为 $\mathrm{Inv}\left(a_1,a_2\cdots a_i\right)$，令 $\displaystyle f_{i,j}=\sum\mathrm{Inv}\left(a_1,a_2\cdots a_i\right)^j$

$$ \begin{aligned} f_{i,j}&=\sum\left(\mathrm{Inv}\left(a_1,a_2\cdots a_{i-1}\right)+\sum_{t=1}^{i-1}\left[a_i\lt a_t\right]\right)^j \\ &=\sum\sum_{l=0}^j\binom{j}{l}\mathrm{Inv}\left(a_1,a_2\cdots a_{i-1}\right)^l\left(\sum_{t=1}^{i-1}\left[a_i \lt a_t\right]\right)^{j-l} \\ &=\sum_{l=0}^j\binom{j}{l}f_{i-1,l}\cdot\left(\sum_{t=0}^{i-1}t^{j-l}\right)\\ &=\sum_{l=0}^j\binom{j}{l}f_{i-1,l}\cdot\left[\dfrac{z^{j-l}}{\left(j-l\right)!}\right]\left(\dfrac{e^{iz}-1}{e^z-1}\right)\\ \end{aligned} $$

设 $f_{i,j}$ 的 EGF 为 $F_i\left(z\right)$

则 $\displaystyle F_i\left(z\right)=\prod_{k=1}^i\dfrac{e^{kz}-1}{e^z-1}$，答案即为 $\displaystyle n!\left[\dfrac{z^{m}}{m!}\right]\prod_{k=1}^n\dfrac{e^{kz-1}}{k\left(e^z-1\right)}$

考虑 $\ln\left(\dfrac{e^{kz}-1}{k\left(e^z-1\right)}\right)=-\ln\left(\dfrac{kz}{e^{kz}-1}\right)+\ln\left(\dfrac{z}{e^z-1}\right)$

观察可得，前面一项的 $z^t$ 的系数是后面那项的 $z^t$ 的系数的 $k^t$ 倍。那么只需求一个自然数幂和最后 $\exp$ 即可。求 $n!$ 可以分段打表。

复杂度 $\mathcal{O}\left(m^2\right)$ 或者 $\mathcal{O}\left(m\log m\right)$

代码

Submission 由于板子太长，就不贴了

文章目录