题目链接:https://ac.nowcoder.com/acm/contest/21791/I
思路:dp+组合数学
首先我们考虑对于单独一层长度为l的方案数是多少
那么我们设f[i][j]表示长度为i,选了j种颜色的方案数(先不考虑排列
那么递推式就是
f[i][j]=f[i-1][j-1]+f[i-1][j]*(j-1)
f[i-1][j-1]代表长度为i-1的时候选了j-1种颜色,那么这个时候必须选个新颜色才能达到j种颜色
f[i-1][j]代表前面选了j种颜色,那么之后选颜色的时候只要不跟最后一个颜色重复就好了,那么就是跟前面j-1中颜色重复那么就乘个(j-1)
之后如果要排列的话乘个j的阶乘就好
之后我们再来考虑到第i层恰好选了j种颜色的情况
先不考虑相邻两层颜色集合不同
设dp[i][j]为第i层恰好选了j种颜色的情况
那么dp[i][j]=
∑
j
=
1
m
i
n
(
L
[
i
−
1
]
,
m
)
\sum_{j=1}^{min(L[i-1],m)}
∑j=1min(L[i−1],m) ×
(
m
j
)
\binom{m}{j}
(jm) × j! × f[L[i]][j]
∑
j
=
1
m
i
n
(
L
[
i
−
1
]
,
m
)
\sum_{j=1}^{min(L[i-1],m)}
∑j=1min(L[i−1],m)代表前i-1层选了所有颜色的方案数
(
m
j
)
\binom{m}{j}
(jm)代表从m个颜色中选j个
之后选了j个颜色进行排列乘上长度为L[i]选了j种颜色的方案数就是dp[i][j](不考虑相邻两层颜色集合不同的情况)
那么如果集合颜色不同呢
我们就可以减去集合颜色相同就是这行选了j种颜色的话上行那肯定不能选j种颜色了
那么就是dp[i][j]-=dp[i-1][j] × j! × f[L[i-1]][j]
可以再弄个滚动数组
之后注意一下取模之类的就好啦
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,mod;
const int N=1e6+10;
ll jc[5050];
ll Cm[5050];
ll L[N];
ll dp[2][5050];
ll f[5050][5050];
ll ans[3];
void init()
{
jc[0]=1;
for(int i=1; i<=m; i++)jc[i]=(jc[i-1]*i)%mod;
Cm[0]=1;
for(int i=1; i<=m; i++)Cm[i]=Cm[i-1]*(m-i+1)%mod;
return;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m>>mod;
init();
for(int i=1; i<=n; i++)cin>>L[i];
f[0][0]=1;
for(int i=1; i<=5000; i++)
for(int j=1; j<=i; j++)f[i][j]=(f[i-1][j-1]+f[i-1][j]*(j-1)%mod)%mod;
int flag=0;
ans[1]=1;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=min(m,L[i]); j++)
{
dp[flag][j]=ans[flag^1]*Cm[j]%mod*f[L[i]][j]%mod;//这里没乘j!是因为和C(j,m)约掉了
if(j<=L[i-1])dp[flag][j]=(dp[flag][j]-dp[flag^1][j]*jc[j]%mod*f[L[i]][j]%mod+mod)%mod;
ans[flag]=(ans[flag]+dp[flag][j])%mod;
}
flag^=1;
ans[flag]=0;
}
cout<<ans[flag^1];
return 0;
}