P7435 简单的排列计数

推歌：Terrasphere

传送

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

对于一个排列 \({\pi_n}\)，定义其一个逆序对为 \(1\le i<j\le n\) 且 \(\pi_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

#include <bits/stdc++.h>
using namespace std;
#define int long long
const 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<<20];
int A[1<<20],B[1<<20],D[1<<20],C[1<<20],E[1<<20];
void init(int n){int lim=1,l=-1;while(lim<=n)lim<<=1,l++;for(int i=1;i<lim;i++)r[i]=(r[i>>1]>>1)|((i&1)<<l);
}
void NTT(int lim,int *a,int opt){//NTT
}
void mult(int n,int m,int *a_tmp,int *b_tmp,int *ans,int tn=-1){//ans=a_tmp*b_tmp
}
void INV(int n,int *p,int *ans){//ans=1/p
}
void ln(int cnt,int *p,int *ans){//ans=ln(p)
}
void exp(int cnt,int *p,int *ans){//ans=exp(p)
}
int fac[200005],ifac[200005];
int p1[1<<20],p2[1<<20],p3[1<<20],p4[1<<20]; 
signed main(){int n,k;cin>>k>>n;fac[0]=1;for(int i=1;i<=n+1;i++)fac[i]=fac[i-1]*i%mod;ifac[n+1]=ksm(fac[n+1],mod-2);for(int i=n+1;i;i--)ifac[i-1]=ifac[i]*i%mod;for(int i=0;i<=n;i++)p1[i]=ksm(k+1,i+1)*ifac[i+1]%mod,p2[i]=ifac[i+1];INV(n+1,p2,p3),mult(n+1,n+1,p3,p1,p1);for(int i=1;i<=n;i++)p1[i]=p1[i]*fac[i-1]%mod;p1[0]=0;for(int i=1;i<=min(n,k);i++){int tmp=ksm(i,i);int mi=tmp;for(int j=1;j*i<=n;j++)p1[i*j]=(p1[i*j]+mod-fac[j-1]*ifac[j]%mod*mi%mod)%mod,mi=mi*tmp%mod;}for(int i=n+1;i<=2*n;i++)p1[i]=0;exp(n+1,p1,p4);for(int i=0;i<=n;i++)cout<<p4[i]<<' ';return 0;
}