正題

---

題目大意

將n個相同球放到k個相同的盒子里，求方案數(shù)。

---

解題思路

其實就是將n劃分成k份，要求前面份的大于等于后面的，所以我們可以寫dp
$f_{i,j}$表示分成i組，分了j。
然后
$$f_{i,j}=f_{i?1,j?1}+f_{i,j?i}$$
$f_{i?1,j?1}$表示分出一個，值為1
$f_{i,j?i}$表示前i份都加上一

這個方程因為后面加的時候前面也會加，就保證了前面的大于等于后面的。

---

code

#include<cstdio> #define ll long long #define XJQ 998244353 using namespace std; ll n,m,f[5010][5010]; int main() {scanf("%lld%lld",&n,&m);f[0][0]=1;for(ll i=1;i<=m;i++)for(ll j=i;j<=n;j++)f[i][j]=(f[i][j-i]+f[i-1][j-1])%XJQ;printf("%lld",f[m][n]); }

總結(jié)

以上是生活随笔為你收集整理的nssl1247-A【dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。