同机房大佬minxu讲解了这个题，使蒟蒻我受益匪浅。
再加上蒟蒻写的计数DP题不超过 0 道，所以遇到这种好题赶紧写题解加深印象。
Solution
因为每一层之间是有互相影响的，所以不能直接用组合数求解，考虑使用计数DP。
我们先处理只在一行内的彩球的方案数
设 (g_{i,j}) 表示有 (i) 个小球串起来，一共用了 (j) 种颜色的方案数。
因为每种颜色是等价的，所以我们可以强制给每个颜色一个编号，并使得编号小的第一次出现在前面，大的在后面。因为这样可以使得转移的时候简单一些，最后求答案的时候乘上一个阶乘即可（他们都说这叫最小表示法）。
现在我们可以写转移方程：
意思是可以在 (i-1) 个小球后加一个新颜色的小球或者加一个和第 (i-1) 个颜色不一样的小球，有 (j-1) 种颜色选择。
再思考行与行之间的影响
设 (f_{i,j}) 为前 (i) 行，其中第 (i) 行选了 (j) 种颜色的方案数。
如果没有题目中的那个限制，是有一个比较显然的转移方程：
意思就是在前 (i-1) 层可能的状态基础上，从 (m) 种颜色中选出 (j) 种来构成第 (i) 层
那么加上了限制，就是：
其实就是减去了一个 (i-1) 层和 (i) 层颜色完全相同的情况
此时再把一直没加上的阶乘加上就是 (f_{i,j}=j!cdotleft(inom mjg_{l_i,j} imes sum_{k=1}^{min(l_{i-1},m)} f_{i-1,k}-g_{l_i,j} imes f_{i-1,j} ight))
而最后的答案是 (ans=sum_{i=1}^{min(m,l_n)}f_{n,i})
完结撒发
等等，不会你以为这就完了吧
last but not least
-
当你敲着敲着发现：因为一个没确定的 (p) ， (inom mj) 仿佛一个毒瘤。你想起了 (exLucas) 这种代码可能比DP转移方程代码还长的东西。
但是我们其实不需要。
因为将 (j!) 扔回括号里，原式就会变成 (f_{i,j}=A_m^j imes g_{l_i,j} imes sum_{k=1}^{min(l_{i-1},m)} f_{i-1,k}-j! imes g_{l_i,j} imes f_{i-1,j})
此时预处理 (A_m^j) 和 (j!) 即可。
-
现在你打完了整个程序，满心欢喜的交上去，会
更欢喜发现它T飞了，所以我们还得优化时间复杂度。观察方程可以发现 (sum_{k=1}^{min(l_{i-1},m)}f_{i-1,k}) 才是让你时间复杂度变成 (O((sum l_i)^2)) 的罪魁祸首。优化方式是在 (i-1) 层记录前缀和，这样就可以做到 (O(1)) 转移。
-
终于，你开开心心的加上了前缀和，又交了上去，正准备和机房同学炫耀的时候，发现它又M飞了，仔细一看内存是 (250MB) ，所以还得优化空间复杂度。
继续看方程吧。又发现 (g) 数组在 (f) 转移的时候有大用，但是 (f) 只和它的前一层有关系，所以将可以将它的前一维抹去。
还有细微的小优化，因为 (A_m^j) 中底下的 (m) 是不变的，只有 (j) 会变，所以这也是个一维数组(●'◡'●)。
时间复杂度： (O(sum l_i)+O(l_i^2)) ，空间复杂度： (O(l_i^2+m))
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int L=5010,N=1e6+10;
int n,m,p;
ll A[N],l[N],f[L],fac[L],tmp[L];//tmp就是滚动数组
int g[L][L];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
inline void init(){
A[0]=1;
for(int i=1;i<=m;i++)
A[i]=A[i-1]*(m-i+1)%p;
g[0][0]=1;
for(int i=1;i<=5000;i++)
for(int j=1;j<=min(i,m);j++){
g[i][j]=(ll)g[i-1][j]*(j-1)%p+g[i-1][j-1];
g[i][j]%=p;
}
fac[0]=1;
for(int i=1;i<=5000;i++) fac[i]=fac[i-1]*i%p;
}
int main(){
n=read();m=read();p=read();
init();
for(int i=1;i<=n;i++) l[i]=read();
ll sum=1,res;
for(int i=1;i<=n;i++){
res=0;
for(int j=1;j<=l[i];j++)
f[j]=(sum*A[j]%p*g[l[i]][j]%p-g[l[i]][j]*tmp[j]%p*fac[j]%p+p)%p,
//防止减法出现负数，所以+p
res=(res+f[j])%p;
sum=res;
for(int j=1;j<=l[i-1];j++) tmp[j]=0;
for(int j=1;j<=l[i];j++) tmp[j]=f[j];
}
printf("%lld
",sum);
return 0;
}
看到这里的小伙伴一定发现我直接把最后一层的 (sum) 输出了。
观察我前缀和优化时间复杂度的式子 (sum_{k=1}^{min(l_{i-1},m)}f_{i-1,k}) 和最后答案的式子 (sum_{i=1}^{min(l_n,m)}f_{n,i}) ，是不是惊奇的发现他们长得一样。
其实是因为虚无的第 (n+1) 层没有小球，也没有颜色，第 (n) 层怎么选都行^o^/