P7438 更简单的排列计数_题解
缙云山车神
·
·
题解
把多项式 F(x) 写成牛顿级数
F(x)=\sum_{i=0}^{k-1} a_i{x\choose i}
现在问题变成求出答案的每一项，即对于每一个 m(1\leq m\leq n) 和 i(0\le i<k) 求 \sum_{\pi}{\text{cyc}_\pi\choose i}。\pi 是长度为 m 的错排，\text{cyc}_\pi 表示错排的环数。
考虑错排的生成函数，首先我们知道一个环的 EGF 为
H=\sum_{i>0} \frac{(i-1)!}{i!}x^i= \sum_{i>0} \frac{x^i}{i}=-\ln(1-x)
一个错排是由若干个环（无自环）组成的，所以错排的 EGF 为
G=e^{-\ln(1-x)-x}
这道题是要我们求从若干个环中选若干个的答案， 所以加一元 $y$ 表示选了多少个环，于是就表示成
$$
G=e^{(-\ln(1-x)-x)\times(1+y)}
$$
记 $g_{a,b}=[x^ay^b]G$，也就是说长度为 $m$ 的错排中选 $i$ 个环的方案数的和为 $m!g_{m,i}$ ，也就是我们要求的 $\sum_{\pi}{\text{cyc}_\pi\choose i}$ 。
直接暴力上多项式牛迭复杂度就飞了。
在 $G$ 上对 $x$ 求导
$$
G(x)'=\frac{x(1+y)}{1-x}G
$$
那么
$$
(n+1)g_{n+1,k}=\sum_{i=0}^{n-1}g_{i,k}+g_{i,k-1}\\
=n\times g_{n,k}+g_{n-1,k}+g_{n-1,k-1}
$$
$O(nk)$ 递推即可。
```cpp
#include <bits/stdc++.h>
#define N 600005
#define K 102
using namespace std;
typedef long long ll;
const int mod=998244353;
ll g[N][K],n,k,fac[N],inv[N];
ll a[K],A[K][K];
ll ksm(ll x,ll y){
ll res=1;
while(y){
if(y&1) res=res*x%mod;
x=x*x%mod; y>>=1;
}
return res;
}
void init(){
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
inv[n]=ksm(fac[n],mod-2);
for(int i=n-1;i>=0;i--)
inv[i]=inv[i+1]*(i+1)%mod,inv[i+1]=inv[i+1]*fac[i]%mod;
}
void get_G(){
g[2][0]=inv[2],g[2][1]=inv[2];
for(ll i=3;i<=n;i++){
g[i][0]=((i-1)*g[i-1][0]%mod+g[i-2][0])*inv[i]%mod;
for(int j=1;j<k;j++)
g[i][j]=((i-1)*g[i-1][j]%mod+g[i-2][j]+g[i-2][j-1])*inv[i]%mod;
}
}
ll get_A(ll x){
ll res=0,X=1;
for(int i=0;i<k;i++,X=X*x%mod) res=(res+X*a[i]%mod)%mod;
return res;
}
int main(){
// freopen("test.in","r",stdin);
cin>>n>>k;
init();
get_G();
for(int i=0;i<k;i++) cin>>a[i];
for(int i=0;i<k;i++) A[0][i]=get_A(i);
for(int i=k,op=1;i>1;i--,op++)
for(int j=0;j<i-1;j++)
A[op][j]=(A[op-1][j+1]-A[op-1][j]+mod)%mod;
for(int i=0;i<k;i++) a[i]=A[i][0];
for(int m=1;m<=n;m++){
ll res=0;
for(int i=0;i<k;i++)
(res+=g[m][i]%mod*a[i]%mod)%=mod;
cout<<fac[m]*res%mod<<' ';
}
}
```