P7435 简单的排列计数

推歌：Terrasphere
传送
首先没推过很多大式子的看到题面会晕，不过没事我们可以它翻译成可读题面。

对于一个排列 \({\pi_n}\)，定义其一个逆序对为 \(1\le i\pi_j\) 的二元组 \((i,j)\)，逆序对 \((i,j)\) 的权值为 \(\pi_i\)，排列的权值为所有逆序对权值之积，如果没有逆序对则为 \(1\)。
给定正整数 \(n,k\)，对于每个 \(0\le m\le k\)，求所有长度为 \(n\)，逆序对数量为 \(m\) 的排列权值之和。

看到这个逆序对可以想到 dp！设 \(dp_{i,j}\) 表示 \(n=i,m=j\) 时的答案。
然后我们考虑转移时在 \(1\sim i-1\) 中插入 \(i\)，发现对答案的贡献只和插入的位置有关！所以我们考虑在哪里插入，再乘上多的贡献，由此得到：

\[dp_{i,j}=\sum_{k=0}^{i-1}i^k dp_{i-1,j-k}\]
当下标为负时值为 \(0\)。
此时我们发现这个式子就是提高组前两个题的难度，十分的没有水平，所以问题肯定不止这么简单。确实是这样，因为这个式子是 \(O(nk^2)\) 的，直接运行可以得到 \(13\) 分的高分！
我们开始观察这个式子，发现是一个卷积，NTT 可以优化，但是啥用没有。
诶，但是既然想到多项式科技了，那我们可以求一下这一行的 GF？
设第 \(i\) 行的 GF 为 \(F_i(x)\)，根据转移方程我们有 \(F_i(x)=F_{i-1}(x)\sum_{j=0}^{i-1}i^jx^j\)，看起来还是不怎么优美。
别急！我们发现 \(\sum_{j=0}^{i-1}i^jx^j\) 是一个等比数列求和，这个东西等于 \(\frac{1-i^ix^i}{1-ix}\)。于是最终我们得到了 \(F_i(x)=F_{i-1}(x)\frac{1-i^ix^i}{1-ix}\)，\(F_n(x)=\prod_{i=1}^n\frac{1-i^ix^i}{1-ix}\)，只需要求出这个东西的系数就好了！
但是这个分数很烦人啊！因此直接就是 \(\ln\) 再 \(\exp\) 转成求和，变成：

\[\exp(\sum_{i=1}^n(\ln(1-i^ix^i)-\ln(1-ix)))\]
我们发现 \(\sum_{i=1}^n\ln(1-i^ix^i)\) 怎么这么熟悉呢？这不是经典背包 P4389 嘛！所以这一部分就变成 \(-\sum_{i=1}^n\sum_{j=1}\frac{(ix)^{ij}}{j}\)，跑一遍调和级数就好了。
接下来开始展开后半部分：

\[\begin{aligned}\sum_{i=1}^n\ln(1-ix)&=-\sum_{i=1}^n\sum_{j=1}\frac{(ix)^j}{j}\\&=-\sum_{j=1}\sum_{i=1}^n\frac{x^j}{j}i^j\\&=-\sum_{j=1}\frac{x^j}{j}\sum_{i=1}^ni^j\\&=-\sum_{j=1}\frac{x^j}{j(j+1)}\sum_{i=0}^j \binom{j+1}{i}B_i(n+1)^{j-i+1}\end{aligned}\]
\(B_i\) 为伯努利数第 \(i\) 项，直接求系数即可。
然后 \(\exp\) 一次就回去了，完结撒花！
code[code]#include using namespace std;#define int long longconst int mod=998244353;int ksm(int a,int q){        int res=1;        while(q){                if(q&1)res=res*a%mod;                a=a*a%mod;                q>>=1;        }         return res;}int Ceilb(int x){        while(x&x-1)x+=x&-x;        return x;}const int iG=ksm(3,mod-2);int r[1

热心回复！