将n拆分成任意个无标号正整数（也可认为是排好序）的方案数记为\(P_n\)
暴力DP——\(O(n^2)\)
两种考虑方式，第一维都是总和，对于第二维，一种是考虑前j种数，另一种是分成j个数。即第一种是完全背包，第二种是考虑最小的数是否为1转移。
数据分治优化——\(O(n\sqrt{n})\)
注意到两种DP的效率分别是\(O(n\times 拆成数的值域大小/拆成数的个数)\)，考虑经典的数据分治优化:
对于前者只考虑在值域$ \sqrt n $内的数；
那么剩下的大于\(\sqrt{n}\)的数，就不会超过\(\sqrt{n}\)，就可以用第二个DP了！
至此，已经得到了比较实用的做法，即码量较小的\(O(n\sqrt{n})\)。
（664B）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=505,P=998244353;
void A(int& x,int y){
x+=y;
if(x>=P) x-=P;
}
int n,m,f[N][2],g[N][2],s[N];
int main()
{
cin>>n;
m=(int)(sqrt(n)+0.5);
f[0][0]=1;
for(int j=1;j<=m;j++){
int p=(j&1);
for(int i=0;i<=n;i++){
f[i][p]=f[i][!p];
if(j<=i) A(f[i][p],f[i-j][p]);
if(j==m) g[i][0]=f[i][p],s[i]=f[i][p];
}
}
for(int j=1;j<=n/m;j++){
int p=(j&1);
for(int i=0;i<=n;i++){
if(i>=m+1) g[i][p]=g[i-1-m][!p];
else g[i][p]=0;
if(j<=i) A(g[i][p],g[i-j][p]);
A(s[i],g[i][p]);
}
}
for(int i=1;i<=n;i++) printf("%d\n",s[i]);
return 0;
}
为了追求极致（防止丧病出题人），还是要研究一下最优的log做法。
多项式做法（五边形数定理）——\(O(nlogn)\)
考虑生成函数，容易发现拆分数对应的多项式是\(\prod_{i=1}^n 1-x^i\)的逆，而这个式子有个神奇的结论：
\(\prod_{i=1}^n 1-x^i=\sum_{i=-\infty}^{+\infty}(-1)^ix^{\frac{i(3i-1)}{2}}\)
由于最后的指数是五边形数，故称为五边形数定理。
发现指数是i的平方级别，那么枚举绝对值在\(\sqrt{n}\)内的i（具体的，稍作放缩可得\(\sqrt{\frac{2}{3}n}\)），然后求逆即可。
好像套个板子就没了，比根号的还好写。
（2249B）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20)+5,P=998244353,G[2]={3,(P+1)/3};
inline int fpw(int a,int x){
int s=1;
for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
return s;
}
int rv[N],gp[2][N],iv[N],fc[N],fv[N];
void init(int n){
fc[0]=1;
for(int i=1;i<n;i++) iv[i]=fpw(i,P-2),fc[i]=1ll*fc[i-1]*i%P;
fv[n-1]=fpw(fc[n-1],P-2);
for(int i=n-2;~i;i--) fv[i]=1ll*fv[i+1]*(i+1)%P;
for(int p=0;p<2;p++){
for(int i=1;i<n;i<<=1){
gp[p][i]=1;
int t=fpw(G[p],(P-1)/(i<<1));
for(int j=i+1;j<(i<<1);j++) gp[p][j]=1ll*gp[p][j-1]*t%P;
}
}
}
void print(char name[],int n,int* a){
printf("%s n=%d\n",name,n);
for(int i=0;i<n;i++) cout<<a[i]<<" "; puts("");
}
inline void dft(int* a,int n,int p){
for(int i=0;i<n;i++) if(i<rv[i]) swap(a[i],a[rv[i]]);
for(int i=1;i<n;i<<=1){
for(int j=0;j<n;j+=(i<<1)){
for(int k=0;k<i;k++){
int &A=a[i+j+k],&B=a[j+k],t=1ll*gp[p][i+k]*A%P;
A=B-t; if(A<0) A+=P;
B=B+t; if(B>=P) B-=P;
}
}
}
if(p) for(int i=0;i<n;i++) a[i]=1ll*a[i]*iv[n]%P;
}
inline int Rev(int m){
int p=0,n=1;
while(n<m) n<<=1,p++;
for(int i=0;i<n;i++) rv[i]=(rv[i>>1]>>1)|((i&1)<<(p-1));
return n;
}
inline void poly_mul(int m,int* A,int* B,int* C){
int n=Rev(m);
dft(A,n,0); dft(B,n,0);
for(int i=0;i<n;i++) C[i]=1ll*A[i]*B[i]%P;
dft(C,n,1);
fill(C+m,C+n,0);
}
int C[N],D[N];
inline void poly_inv(int m,int *a, int *b) {
if(m==1){
b[0]=fpw(a[0],P-2);
return;
}
poly_inv((m + 1)>>1,a,b);
int n=Rev(m<<1);
copy(a,a+m,C);
fill(C+m,C+n,0);
dft(b,n,0); dft(C,n,0);
for(int i=0;i<n;i++) b[i]=1ll*b[i]*(P+2-1ll*b[i]*C[i]%P)%P;
dft(b,n,1);
fill(b+m,b+n,0);
}
void A(int& x,int y){
x+=y;
if(x>=P) x-=P;
}
int n,m,a[N],b[N];
int main(){
init(1<<19);
cin>>n;
m=(int)(sqrt(n*2/3+1)+0.5);
for(int i=-m;i<=m;i++){
int t=i*(3*i-1)/2;
if(t>n) continue;
if(abs(i)&1) A(a[t],P-1);
else A(a[t],1);
}
poly_inv(n+1,a,b);
for(int i=1;i<=n;i++) printf("%d\n",b[i]);
return 0;
}
原文链接: https://www.cnblogs.com/szsz/p/17050503.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/311864
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
