command_block 的博客

command_block 的博客

[DP记录]ABC221H Count Multiset

posted on 2021-11-19 07:18:47 | under 记录 |

题意 : 对于每个 $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)$。

#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;
}