题解 | #New Year Garland#

一个比较套路的题，难度是 * $2600$ ，只能说不算太难吧。读完这篇题解后，希望大家都能有所收获！

套路地，我们分层来考虑问题。我们将问题分为两个部分，即层内预处理、层与层之间的转移。

层内预处理：即我们需要计算用 $j$ 种颜色填充长度为 $L$ 的一层的方案数。设 $f_{i, j}$ 表示使用了 $j$ 种颜色，填充了长度为 $i$ 的行，且相邻颜色不同的方案数（进考虑先对颜色模式，不考虑具体颜色值）。则我们有 $g_{i, j} = g_{i - 1, j - 1} + g_{i - 1, j} \times (j - 1)$ 。

假设我们选定了特定的 $j$ 种颜色，则填充长度为 $L$ 的一层的方案数为： $g_{L, j} \times j!$ 。预处理的范围是 $1 \le j \le i \le 5000$ ，可以接受。

再说第二部分，即层与层之间的转移：设 $f_{i, j}$ 表示考虑到第 $i$ 层，且第 $i$ 层已经恰好使用了 $j$ 种颜色的方案数。首先，对于第 $i$ 层，我们想选 $j$ 种颜色，方案数是 $G(i, j) = g_{i, j} \times j! \times C(m, j)$ 。

由状态定义，我们有以下转移逻辑：总方案数 $=$ （前 $i - 1$ 层的所有方案） $\times$ （第 $i$ 层使用任意方案） $-$ 冲突方案。这里的冲突方案所要满足的条件是：

$i - 1$ 层用的颜色数量也是 $j$ 。
颜色集完全相同，考虑列式子：
- 首先是在 $i - 1$ 行使用特定的某组 $j$ 个颜色的方案数： $\frac{f_{i - 1, j}}{\binom{m}{j}}$ 。
- 在第 $i$ 层中使用上述方案的方案数是： $g_{l_i, j} \times j!$ 。
- 对所有可能的情况求和，即冲突的总数为： $\binom{m}{j} \times \frac{f_{i - 1, j}}{\binom{m}{j}} \times g_{l_i, j} \times j! = f_{i - 1, j} \times g_{l_i, j} \times j!$ 。

则我们有最终的 $DP$ 转移方程： $f_{i, j} = g_{l_i, j} \times j! \times \binom{m}{j} \times \sum_k f_{i - 1, k} - f_{i - 1, j} \times g_{l_i, j} \times j!$ ，化简后就是： $f_{i, j} = \large g_{l_i, j} \times j! \times (\binom{m}{j} \times \sum_k f_{i - 1, k} - f_{i - 1, j})$ 。直接把 $\sum_k f_{i - 1, k}$ 优化掉，然后再把空间滚动一下即可。

时间复杂度： $O(\max(l_i)^2 + \displaystyle \sum_{i = 1}^n l_i + n)$ 。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5010, M = 1e6 + 10;
int g[N][N], P[N];
int l[M], fact[N];
int old[N], nw[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, p;
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++) {
        cin >> l[i];
    }
    g[0][0] = 1, g[1][1] = 1;
    for (int i = 2; i < N; i++) {
        for (int j = 1; j <= i; j++) {
            g[i][j] = (g[i - 1][j - 1] + g[i - 1][j] * (j - 1)) % p;
        }
    }
    P[0] = fact[0] = 1;
    for (int i = 1; i < N; i++) {
        P[i] = P[i - 1] * (m - i + 1) % p;
        fact[i] = fact[i - 1] * i % p;
    }
    int sum = 0;
    for (int i = 1; i <= min(m, l[1]); i++) {
        old[i] = P[i] * g[l[1]][i] % p;
        sum = (sum + old[i]) % p;
    }
    for (int i = 2; i <= n; i++) {
        int nw_sum = 0;
        for (int j = 1; j <= min(m, l[i]); j++) {
            int val1 = P[j] % p * sum % p;
            int val2 = 0;
            if (j <= min(m, l[i - 1])) {
                val2 = fact[j] % p * old[j] % p;
            }
            nw[j] = g[l[i]][j] * (val1 - val2 + p) % p;
            nw_sum = (nw_sum + nw[j]) % p;
        }
        sum = nw_sum;
        memcpy(old, nw, sizeof(nw));
    }
    cout << (sum + p) % p << "\n";
    return 0;
}