本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-16 17:12:37

:::::info[题目基本信息] 考察：组合数学，动态规划 DP（$2780$）。
题目简介：
给定 $\{a_n\}$，求有多少 $\{b_n\}$ 满足（对 $998244353$ 取模）：

• $\forall i\in[1,n],b_i\in[1,n]$
• $\forall i\in[1,n],\sum_{j=1}^n[b_j=i]\le a_i$
• $\forall i\in[1,n],\sum_{j=1}^n[b_j=b_i]\le a_i$

数据范围：

• $1\le n\le 500$
• $\forall i\in[1,n],1\le a_i\le n$ ::::: 通过尝试我们发现朴素地对位置 DP 或者连续段 DP 都是不行的，所以我们换一种思路，考虑对限制进行 DP，那么我们注意到一个优美的性质，如果我们按一个数在 $\{b_n\}$ 的出现次数降序决策，那么它们之间的影响和干扰不大，所以我们尝试这条道路。
  具体地，设 $f_{i,j,k}$ 表示考虑到所有在 $\{b_n\}$ 中出现次数不低于 $i$ 的数，一共有 $j$ 个，一共出现了 $k$ 次，考虑枚举出现次数恰好为 $i$ 的数的个数为 $l$，那么我们需要转移到 $f_{i-1,j+l,k+(i-1)l}$ ，设 $t_i=\displaystyle\sum_{j=1}^n[a_j\ge i]$，那么我们需要在 $t_{i-1}-j$ 种还没填的数里面选 $l$ 种数进行一个填，然后在 $t_{i-1}-k$ 个位置里选 $(i-1)l$ 个进行一个填，然后排列一下顺序，所以最终的转移方程式为：
  $$f_{i-1,j+l,k+(i-1)l}\leftarrow \binom{t_{i-1}-j}{l}\binom{(i-1)l}{l,l,\dots,l}\binom{t_{i-1}-k}{(i-1)l}f_{i,j,k}$$ 这样的话正确性是有保证的，复杂度是多少呢？
  容易发现 $j,l$ 都是 $\dfrac{n}{i}$ 级别，那么复杂度满足这样一个式子，然后我们将其推导：
  $$\begin{aligned}\sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}\sum_{k=1}^n\sum_{l=1}^{\frac{n}{i}}1&=\sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}\sum_{k=1}^n\frac{n}{i}\&=\sum_{i=1}^n\frac{n^3}{i^2}\&=n^3\sum_{i=1}^n\frac{1}{i^2}\end{aligned}$$ 那么 $\displaystyle\sum_{i=1}^n\frac{1}{i^2}$ 是多少呢？
  :::::success[关于上式结果为常数的说明] 有个定理是 $\displaystyle\sum_{i=1}^{\infty}\frac{1}{i^2}=\frac{\pi^2}{6}$，但是关于它的证明太魔怔，所以我们不要用上面的定理。
  注意到我们不需要太精确，所以我们可以适当放缩：
  $$\begin{aligned}\sum_{i=1}^n\frac{1}{i^2}&=1+\sum_{i=2}^n\frac{1}{i^2}\&\le1+\sum_{i=2}^{n}\frac{1}{i(i-1)}\&=1+\sum_{i=2}^n\frac{1}{i-1}-\frac{1}{i}\&=1+\frac{1}{1}-\frac{1}{n}\&<2\end{aligned}$$ 所以这个东西只是常数复杂度。
  ::::: 综上，时空复杂度均为 $\Theta(n^3)$。

code