大意

$n$个球，$m$个盘，盘子不能空，求本质上不相同的方案数

---

思路

首先深搜

#include<cstdio> using namespace std;int n,m,ans; inline void dfs(register int dep,register int sy,register int last) { if(dep==m+1){ans++;return;}//分完了，统计 if(dep<m) for(register int i=last;i<=sy;i++)dfs(dep+1,sy-i,i);//继续分 else if(sy>=last)dfs(dep+1,0,sy);//剩下的直接分完 } signed main() { scanf("%d%d",&n,&m);//输入 dfs(1,n,1);//dfs printf("%d",ans);//输出 }

然后发现规律$f[i][j]=f[i-1][j-1]+f[i-j][j]$

当然，你也可以这样想： 当前的方案数=少一个球少一个盒+少盒子个球盒子数不变的方案数（因为要保证满足本质上不同，否则的话就是$f[i-1][j]$，就变成杨辉三角了就可以愉快的跑费小了

---

代码

#include<cstdio> #define ymw 998244353 using namespace std;int n,m; typedef long long LL; LL f[5001][5001]; signed main() { scanf("%d%d",&n,&m); for(register int i=1;i<=n;i++) { f[i][1]=1;f[i][2]=i/2; for(register int j=3;j<=i;j++) (f[i][j]=f[i-1][j-1]+f[i-j][j])%=ymw;//动态转移 } printf("%lld",f[n][m]);//输出 }