分拆数简介

分拆数是对正整数 $n$ 进行无序分拆的方案数。

举个例子，对 $5$ 进行分拆，有以下几种方案。

• $1+1+1+1+1$
• $2+1+1+1$
• $2+2+1$
• $3+1+1$
• $3+2$
• $4+1$
• $5$

如何求分拆数呢？

方法

前置知识：生成函数，多项式科技。

考虑选若干 $i$，那么它们的和是 $i$ 的倍数或 $0$。所以可以写出生成函数 ∑ j = 0∞x i j \sum\limits_{j=0}^{\infty}x^{ij}j=0∑∞​xij

因为 1 1−x = ∑ j = 0∞xj \dfrac{1}{1-x}=\sum\limits_{j=0}^{\infty}x^j1−x1​=j=0∑∞​xj，把 $x$ 整体替换为 xi x^ixi，就得到 1 1− x i ∑ j = 0∞x i j \dfrac{1}{1-x^i}\sum\limits_{j=0}^{\infty}x^{ij}1−xi1​j=0∑∞​xij

如果选多个数，那么就是把 $1\sim n$ 对应的生成函数乘起来。

设 $A(x)$ 表示 $x$ 的分拆数，则 A ( x ) =1∏ i=1∞(1− x i)A(x)=\dfrac{1}{\prod\limits_{i=1}^{\infty}(1-x^i)}A(x)=i=1∏∞​(1−xi)1​

直接求这个 $A(x)$ 是很慢的，我们要优化它。

两边取对数得
ln⁡A(x)=− ∑ i=1∞ln⁡(1− x i)\ln A(x)=-\sum\limits_{i=1}^{\infty}\ln(1-x^i) lnA(x)=−i=1∑∞​ln(1−xi)

设 f ( x ) = − ∑ i = 1∞ln ⁡ ( 1 − xi)f(x)=-\sum\limits_{i=1}^{\infty}\ln(1-x^i)f(x)=−i=1∑∞​ln(1−xi)

对 $f(x)$ 求导得
f ′(x) = ∑ i=1∞ i x i−1 1− x i= ∑ i=1∞i x i−1∑ j=0∞ x ij= ∑ i=1∞ ∑ j=0∞i x i(j+1)−1= ∑ i=1∞ ∑ j=1∞i x ij−1 \begin{aligned} f'(x)&=\sum\limits_{i=1}^{\infty}\dfrac{ix^{i-1}}{1-x^i}\\ &=\sum\limits_{i=1}^{\infty}ix^{i-1}\sum\limits_{j=0}^{\infty}x^{ij}\\ &=\sum\limits_{i=1}^{\infty}\sum\limits_{j=0}^{\infty}ix^{i(j+1)-1}\\ &=\sum\limits_{i=1}^{\infty}\sum\limits_{j=1}^{\infty}ix^{ij-1}\\ \end{aligned} f′(x)​=i=1∑∞​1−xiixi−1​=i=1∑∞​ixi−1j=0∑∞​xij=i=1∑∞​j=0∑∞​ixi(j+1)−1=i=1∑∞​j=1∑∞​ixij−1​

所以 f ( x ) = ∑ i = 1∞∑ j = 1∞ x i jj= ∑ i = 1∞xi∑ d ∣ i 1 d f(x)=\sum\limits_{i=1}^{\infty}\sum\limits_{j=1}^{\infty}\dfrac{x^{ij}}{j}=\sum\limits_{i=1}^{\infty}x^i\sum\limits_{d\mid i}\dfrac{1}{d}f(x)=i=1∑∞​j=1∑∞​jxij​=i=1∑∞​xid∣i∑​d1​

容易观察到求出全部系数的时间复杂度为 $O(n\ln n)$

又有 A ( x ) = e f ( x ) A(x)=e^{f(x)}A(x)=ef(x)

用欧拉筛求出 $f(x)$ 的系数后，再用多项式 $\exp$ 求答案即可。

总的时间复杂度为 $O(n\log n)$

例题

LOJ6268 分拆数

板题，代码如下：

#includeusing namespace std;typedef long long ll;const int N=(1<<18)+1;const ll mod=998244353,g=3,inv2=499122177;int len=1,n;ll a1[N],w,wn,a[N],ans[N],invans[N],lnans[N],da[N],inva[N],omg[N],inv[N];ll ksm(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;}void change(ll num[]){for(int i=1,j=len/2;i<len-1;i++){if(i<j) swap(num[i],num[j]);int k=len/2;while(j>=k) j-=k,k>>=1;if(j<k) j+=k;}}void ntt(ll num[],int fl){for(int i=2;i<=len;i<<=1){if(fl==1) wn=ksm(g,(mod-1)/i);else wn=ksm(g,mod-1-(mod-1)/i);for(int j=0;j<len;j+=i){w=1;for(int k=j;k<j+i/2;k++){ll u=w*num[k+i/2]%mod,t=num[k];num[k]=(t+u)%mod;num[k+i/2]=(t-u+mod)%mod;w=w*wn%mod;}}}if(fl==-1){ll inv=ksm(len,mod-2);for(int i=0;i<len;i++) num[i]=num[i]*inv%mod;}}int read(){int sum=0,c=getchar();while(c<48||c>57) c=getchar();while(c>=48&&c<=57) sum=sum*10+c-48,c=getchar();return sum;}void getinv(int n,ll a[],ll ans[]){if(n==1){ans[0]=ksm(a[0],mod-2);return;}getinv((n+1)/2,a,ans);len=1;while(len<2*n) len*=2;for(int i=0;i<n;i++) a1[i]=a[i];for(int i=n;i<len;i++) a1[i]=0;change(a1),change(ans);ntt(a1,1),ntt(ans,1);for(int i=0;i<len;i++) ans[i]=ans[i]*(2-ans[i]*a1[i]%mod+mod)%mod;change(ans),ntt(ans,-1);for(int i=n;i<len;i++) ans[i]=0;}void getln(int n,ll a[],ll ln[]){for(int i=1;i<n;i++) da[i-1]=a[i]*i;da[n-1]=0;memset(inva,0,sizeof(inva));getinv(n,a,inva);len=1;while(len<2*n) len*=2;change(da),change(inva);ntt(da,1),ntt(inva,1);for(int i=0;i<len;i++) ln[i]=da[i]*inva[i]%mod;change(ln),ntt(ln,-1);for(int i=len-1;i>=0;i--) ln[i+1]=ksm(i+1,mod-2)*ln[i]%mod;for(int i=n;i<len;i++) ln[i]=0;ln[0]=0;}void getexp(int n,ll a[],ll ans[]){if(n==1){ans[0]=1;return;}getexp((n+1)/2,a,ans);len=1;while(len<2*n) len*=2;// memset(lnans,0,sizeof(lnans));getln(n,ans,lnans);for(int i=0;i<n;i++) lnans[i]=(-lnans[i]+a[i]+mod)%mod;lnans[0]++;change(ans),change(lnans);ntt(ans,1),ntt(lnans,1);for(int i=0;i<len;i++) ans[i]=ans[i]*lnans[i]%mod;change(ans),ntt(ans,-1);for(int i=n;i<len;i++) ans[i]=0;}void init(int n){inv[1]=1;for(int i=2;i<=n;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;}int main(){init(1e5);scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;i*j<=n;j++){(a[i*j]+=inv[j])%=mod;}}getexp(n+1,a,ans);for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);}

建议阅读我的下一篇博客再谈分拆数