Case 1: $n,m \leq 10$

考虑枚举每一个数出现了多少次，然后简单计算众数和概率即可。

Case 2：$m,m \leq 20$

也许存在一些 $2^n$ 做法，但是出题人没有想到啥好的实现。

Case 3：$n \leq 100$

这一档是留给一些实现比较差的正解，或者一些奇奇怪怪没有跑过的多项式做法。

一句题外话，这道题出题人只想到了一个 $\Theta(n^2 \log^2 n)$ 的做法，感觉没有啥意思。但是还是非常良心的把模数设成了 $998244353$, 如果选手有非常美妙的多项式做法也可以分享一下。

同时发现，这道题的 $m$ 其实是不重要的，在 $m$ 很小的时候也许在某些地方可以减少一些代码实现，但这都是平凡的。

Case 4：$n \leq 10^3,m \leq 10^9$

考虑正解，首先我们考虑描述众数的方式：$\max_i f_i$，其中 $f_i$ 是 $i$ 在序列中的出现次数。

于是我们考虑 $min\_max$ 容斥，$U=\{1,2, \dots m\}$，尝试计算 $\sum_{S \subseteq U,S \neq \emptyset} (-1)^{|S|-1} \min_{j \in S} f_j$.

更进一步的观察，我们只关心 $|S|$，也就是 $S$ 的大小，换句话说，也就是序列里出现数的种类数。

假设序列里出现了 $k$个数，并且出现次数分别是 $a_1,a_2, \dots a_k$，贡献的系数就是 $(-1)^{k-1} \binom{m}{k} k! \frac{n!}{\prod a_i!} \min_i a_i$。

对于 $\min$ ，我们改为对于每一个 $k$，计算 $min>=k$ 的方案数。

而计算 $(-1)^{k-1} \binom{m}{k} k! \frac{n!}{\prod a_i!}$ 会出现一些神秘多项式做法，但是出题人在这里要介绍的是另一种做法。

考虑因为我们的条件是 $\min \geq k$，于是我们考虑从大到小枚举一个出现次数，然后尝试用动态规划来解决问题。

设 $f_{v,i,j}$ 表示考虑完了出现次数 $\geq v$ 的数，目前出现了 $i$ 种数，一共有 $j$ 个。

考虑转移，直接枚举一共有多少个数的出现次数为 $v$，然后直接转移。

考虑这份代码的时间复杂度，这里其实我们可以用一个程序计算我们需要执行的循环次数，如下：

rf(v,n,1)
    fr(j,0,min(n/v,m))
        fr(k,j*v,n)
            ans+=(n-k)/v;

跑完之后发现 $n=10^3$ 时循环次数只有 $2 \times 10^8$ 左右，并且这个数不一定取得到，最后实际的次数一定比这个少，于是直接按照最暴力的方式转移就可以了。

然后注意一下转移的系数，推一下并不是很复杂，这一步留给选手自己计算一下。

时间复杂度 $\Theta(n^3)$，但是这个常数非常的小，可以通过这道题。

后面是一个多项式做法：

1. 期望转化

设随机变量 $X$ 为众数的出现次数，则

$$E[X] = \sum_{k=1}^{n} P(X \ge k).$$

因此只需对每个 $k$ 计算至少有一种数出现次数不少于 $k$ 的概率。

2. 容斥原理

固定 $k$，设事件 $A_i$ 表示第 $i$ 种数出现次数 $\ge k$。由容斥原理：

$$P\left(\bigcup_{i=1}^{m} A_i\right) = \sum_{t=1}^{\min(m,\lfloor n/k \rfloor)} (-1)^{t-1} \binom{m}{t} \cdot P(\text{指定的 }t\text{ 种数均} \ge k). $$

3. 指定 $t$ 种数均 $\ge k$ 的概率

指定 $t$ 种数，记它们的总出现次数为 $s$（显然 $s \ge tk$）。在 $n$ 个独立试验中，选择 $s$ 个位置给这些数，方案数为 $\binom{n}{s}$；将这 $s$ 个位置分配给 $t$ 种数，要求每种至少 $k$ 个，记分配方式数为 $f_t(s)$；剩余 $n-s$ 个位置由其余 $m-t$ 种数任意填充，有 $(m-t)^{n-s}$ 种。因此满足条件的序列总数为

$$\sum_{s=tk}^{n} \binom{n}{s} f_t(s) (m-t)^{n-s}.$$

概率即为该总数除以 $m^n$。

4. 计算 $f_t(s)$

问题等价于将 $s$ 个有标号球放入 $t$ 个有标号盒子，每个盒子至少 $k$ 个球。考虑指数生成函数：

$$A(x) = \sum_{j=k}^{\infty} \frac{x^j}{j!},$$

则

$$f_t(s) = s! \cdot [x^s] \big(A(x)\big)^t.$$

• 当 $k=1$ 时：$A(x) = e^x - 1$，此时 $\big(A(x)\big)^t$ 的系数与第二类斯特林数相关，可利用递推$$f_t(s) = \frac{t}{s} \big( f_t(s-1) + f_{t-1}(s-1) \big) $$在 $O(n^2)$ 时间内计算所有 $f_t(s)$。
• 当 $k>1$ 时：直接计算多项式幂次。由于 $n \le 1000$，可预处理多项式 $A(x)$ 的前 $n+1$ 项，然后通过快速幂（逐次卷积）得到 $A(x)^t$ 的前 $n$ 项系数，卷积用 NTT 加速（长度取 $2n$ 的幂次）。对每个 $t$ 进行卷积，总卷积次数约为 $O(n \log n)$。

5. 整体流程

1. 预处理：阶乘、逆元、组合数 $\binom{m}{t}$（$t \le n$）、$\left(\frac{1}{m}\right)^i$、$(m-t)^i$ 等。
2. 对每个 $k = 1 \dots n$：
   • 计算所有需要的 $f_t(s)$（根据 $k$ 选择方法）。
   • 利用容斥公式累加得到 $P(X \ge k)$。
3. 将所有 $P(X \ge k)$ 求和得到期望。

时间复杂度

• 当 $k=1$ 时，递推求 $f_t(s)$ 复杂度 $O(n^2)$。
• 当 $k>1$ 时，对每个 $t$ 进行一次 NTT 卷积，总卷积次数约为 $\sum_{k=2}^{n} \lfloor n/k \rfloor = O(n \log n)$。单次 NTT 长度为 $O(n)$，复杂度 $O(n \log n)$，因此该部分总复杂度 $O(n^2 \log^2 n)$。
• 容斥求和部分的额外复杂度为 $O(n^2 \log n)$，可忽略。

总时间复杂度为 $O(n^2 \log^2 n)$，对于 $n \le 1000$ 可以在时限内运行。