生成函数 P4463题解

· · 题解

题意很明确。

考虑一个 \rm DP。由于限制了互不相同，那么我们考虑从值域开始想。

设 dp_{n,k} 为在 [1,n] 中选了 k 个数的权值之和。

容易得到有：

dp_{n,k}=\sum_{i=1}^{n-1}dp_{i,k-1} \times n \times (N-k+1)

很明显考虑 0 肯定也没有问题。

接下来开始生成函数：

F_k(x)=\sum_{i=0}^{\infty}dp_{i,k}x^i

首先这个 N-k+1 肯定能放到最后去乘上一个阶乘，于是就变成了计算

dp_{n,k}=\sum_{i=0}^{n-1}dp_{i,k-1} \times n

用 GF 来写的话，因为 n 的存在，考虑求导：

F_k(x)=x(\frac {xF_{k-1}(x)}{1-x})'

然后我们有边界条件 F_0(x)=1，答案是 [x^n]\frac {F_k(x)}{1-x}。

注意到 F_k(x) 一定是类似 \frac {G(x)}{(1-x)^y} 之类的，所以考虑递推 F_k(x)。

根据 F_k(x)=x(\frac {xF_k(x)}{1-x})'，我们直接保存 F_k(x)=\frac {H(x)}{(1-x)^y}，然后暴力计算多项式乘法，除法求导利用 (\frac {F(x)}{G(x)})'=\frac {F'(x)G(x)-F(x)G'(x)}{G^2(x)} 即可。

具体来说，计算这个东西：

(\frac {F(x)}{(1-x)^y})'

我们知道 (F^k(x))'=kF^{k-1}(x)F'(x)：

\frac {F'(x)(1-x)^y+yF(x)(1-x)^{y-1}}{(1-x)^{2y}} \frac {F'(x)(1-x)+yF(x)}{(1-x)^{y+1}}

答案是类似 \frac {F(x)}{(1-x)^{k+1}} 的形式，我们又知道 \frac 1 {(1-x)^{k+1}}=\sum_{i=0}^{\infty}\binom {i+k}ix^i，直接卷就好了。

瓶颈在递推，复杂度 O(k^2)。

别忘记最后要乘上一个阶乘。

#include<cstdio>
typedef unsigned ui;
const ui M=505;
ui n,k,mod,f[M<<1],C[M<<1];
inline ui pow(ui a,ui b){
    ui ans(1);for(a%=mod;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;return ans;
}
signed main(){
    ui i,j,inx,ans(0);scanf("%u%u%u",&k,&n,&mod);C[inx=2*n+1>k?k:2*n+1]=f[0]=1;
    for(i=1;i<=n;f[1]=f[0],f[0]=0,++i)for(j=i*2;j>=2;--j)f[j]=(1ull*f[j-1]*j+f[j-2]*(2ull*i-j))%mod;
    if(inx==2*n+1)for(i=1;i<=2*n;++i)C[inx]=1ull*C[inx]*(k-i)%mod*pow(i,mod-2)%mod;
    for(i=inx-1;i<=2*n;--i)C[i]=C[i+1]*(k+2ull*n-i)%mod*pow(k-i,mod-2)%mod;
    for(i=0;i<=n*2;++i)ans=(ans+1ull*C[i]*f[i])%mod;for(i=1;i<=n;++i)ans=1ull*ans*i%mod;
    printf("%u",ans);
}