New Year Garland(计数类DP)

New Year Garland

题意

​ 用m种颜色的球装饰n层的圣诞树，圣诞树的第i层由$l_i$个彩球串成，且同一层相邻的球颜色不同，相邻的层之间彩球颜色的集合不同，问有多少种方案，对p取模。

分析

​ 首先先计算每一层各种小球选取情况下的方案数，因为限制每层小球只有$l_i$个，且$l_i\le 5000$，所以可以预处理出$g[l_i][j]$表示$l_i$个球中有$j$种颜色时放置的方案数，递推方程就是
$$g[i][j]=g[i-1][j-1]+g[i-1][j]\ast (j-1)$$

边界是$g[0][0]=1$，递推方程的意思是要么在第$i-1$个球后面放一个未出现的颜色的小球，要么放一个已经出现过的颜色的小球，因为相邻颜色不同，所以有$(j-1)$种方式，第i层放j种颜色小球的放置方案数就成了
$$j!\ast \left(\genfrac{}{}{0ex}{}{m}{j}\right)\ast g[l_i][j]$$

​ 然后再考虑层与层之间的限制，假如没有这个限制的话，dp就可以写成
$$dp[i][j]=j!\ast \left(\genfrac{}{}{0ex}{}{m}{j}\right)\ast g[l_i][j]\ast \sum _{k=1}^{min(m,l_{i-1})}dp[i-1][k]$$

加上限制后，只需要减去相同颜色集合的对应方案数即可，那就成了
$$dp[i][j]=j!((\genfrac{}{}{0ex}{}{m}{j})\ast g[l_i][j]\ast \sum _{k=1}^{min(m,l_{i-1})}dp[i-1][k]-g[l_i][j]\ast dp[i-1][j])$$
最终的答案就是
$$ans=\sum _{i=1}^{min(m,l_n)}dp[n][i]$$
现在思考一下能够预处理的是$g[l_i][j]$以及$j!$。$\left(\genfrac{}{}{0ex}{}{m}{j}\right)$好似能预处理出来，又好似因为p不一定是素数，不一定能求逆，尝试把$j!$带入方程观察，发现$\left(\genfrac{}{}{0ex}{}{m}{j}\right)$就变成了$A_m^j$，可以开心的预处理了。前面都解决了，但里面还有一个$dp[i-1][k]$的求和每次都要跑满循环，再次观察能否$O(1)$求出。当然一定是可以边计算边求出上一轮dp的和，所以这个值也可以$O(1)$求出了。边界就是第一轮的dp的和为1。但这就结束了嘛？显然没有:(。因为$n\le 1000000$导致dp数组空间巨大，此时，不难发现，该轮的dp只与上一轮的dp值有关，即好似可以滚动数组优化之类的操作，用两个数组即可完成dp过程。

AC代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int g[5010][5010], fac[5010], fac1[1000010], dp[5010], tmp[5010];
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, p;cin >> n >> m >> p;vector<int> l(n + 1);for (int i = 1; i <= n; i++) {cin >> l[i];}g[0][0] = 1;for (int i = 1; i <= 5000; i++) {for (int j = 1; j <= i; j++) {g[i][j] = (g[i - 1][j - 1] + 1LL * (j - 1) * g[i - 1][j] % p) % p;}}fac[0] = 1;for (int i = 1; i <= 5000; i++) {fac[i] = 1LL * fac[i - 1] * i % p;}fac1[0] = 1;for (int i = 1; i <= m; i++) {fac1[i] = 1LL * fac1[i - 1] * (m - i + 1) % p;}LL sum = 1;for (int i = 1; i <= n; i++) {LL res = 0;for (int j = 1; j <= l[i]; j++) {tmp[j] = (1LL * fac1[j] * g[l[i]][j] % p * sum % p - 1LL * fac[j] * g[l[i]][j] % p * dp[j] % p + p) % p;res = (tmp[j] + res) % p;}sum = res;for (int j = 1; j <= l[i - 1]; j++) {dp[j] = 0;}for (int j = 1; j <= l[i]; j++) {dp[j] = tmp[j];}}cout << sum << '\n';return 0;
}