[DP记录]ABC221H Count Multiset
command_block
2021-11-19 07:18:47
**题意** ： 对于每个 $k=1\sim n$ ，统计满足以下要求的无序集合个数：
- 元素均为正整数。
- 恰有 $k$ 个元素。
- 同一个数最多出现 $m$ 次
- 元素和为 $n$。
答案对 $998244353$ 取模。
$m\leq n\leq 5000$ ，时限$\texttt{2s}$ 。
------------
对于一种方案，将集合中的数从大到小排列，画出直方图。
直方图的上边缘是一条路径，要求如下：
- 从左侧某处出发
- 单调不升
- 围成面积为 $n$
- 最多横向连续移动 $m$ （这个横过来不好做）
- 恰横向移动了 $k$
将该图像转置，仍然得到一条路径，要求如下：
- 从左侧下方某处出发
- 围成面积为 $n$
- 最多纵向连续移动 $m$
- 恰纵向移动了 $k$
考虑 DP ，记 $f[S][x]$ 为下方面积为 $S$ ，目前高度为 $x$ 的方案数。
枚举上一行的高度，转移如下：
$$f[S][x]=\sum\limits_{y=\max(1,x-m)}^xf[S-x][y]$$
前缀和优化，复杂度 $O(n^2)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 5050
using namespace std;
const int mod=998244353;
int n,m,f[MaxN][MaxN],o[MaxN][MaxN];
int main()
{
scanf("%d%d",&n,&m);
o[0][0]=1;
for (int s=1;s<=n;s++){
for (int x=1;x<=s;x++){
f[s][x]=o[s-x][min(x,s-x)];
if (x-m-1>=0)(f[s][x]-=o[s-x][min(x-m-1,s-x)])%=mod;
o[s][x]=(o[s][x-1]+f[s][x])%mod;
}
}
for (int i=1;i<=n;i++)
printf("%d\n",(f[n][i]+mod)%mod);
return 0;
}
```