借鉴:DeepinC
逐层递推:设$dp[i][j]$表示到了第i层,这层用了某$j$种颜色的总方案数。
注意这里为了方便去重,所以dp的含义里是已经确定了j种颜色,所以不要乘上 $C_{m}^j$
那么再设$s[i]$是填到第i曾为止的总方案数那么$s[i]$=$\sum dp[i][j]*C[m][j]$
还需要预处理一下$g$数组,$g[i][j]$表示用恰好$i$种颜色填满$j$个格子的方案数。而这$j$种颜色也是未钦定的所以不带组合数。
那么$dp$的转移式也就有了,$dp[i][j]=(s[i-1]-dp[i-1][j])*g[j][a[i]]$;
只从上一层转移而来所以可以滚动。
$f$的预处理也很简单,转移就是从长度短$1$的状态中选择一种颜色填上。
$g[i][j]=g[i-1][j]*(j-1)+g[i-1][j-1]*j$;即如果不新增颜色的话那么你能从已有的$j$种里除上一位刚填的那一种外其他的颜色里选一种,即j-1。
如果你新开了一种颜色,那么就要决定这新开的一种颜色是现有的$j$种里的哪一种,即乘$j$。
然后想一想简化:当模数不是质数时除法会出问题而加减乘都没事。然而整个代码里只有组合数那一步需要除法。
那么怎么搞掉组合数呢?
$s[i]=\sum dp[i][j]*C[m][j]$,想办法压掉$C[m][j]$。
$dp[i][j]=(s[i-1]-dp[i-1][j])*g[j][a[i]]*C[m][j]=s[i-1]*g[j][a[i]]*C[m][j]-dp[i-1][j]*g[j][a[i]]$
注意,其实这里有点问题,也就是$dp[i][j]$只用乘一次$C[m][j]$,就令$dp[i-1][j]$中含有一个$C[m][j]$即可。
因此$dp[i][j]=s[i-1]*g[j][a[i]]*C[m][j]-dp[i-1][j]*g[j][a[i]]$
需要一些脑洞,我们新开一个数组
$f[i][j]=f[i-1][j-1]*(m+1-j)+f[i-1][j]*(j-1)$
恰好替代了
$g[j][a[i]]*C[m][j]$。
#include<cstdio>
#define ll long long
int n,p,m,a[1000005],f[5005][5005],dp[5005],g[5005][5005],ld;
main(){
freopen("kalanchoe.in","r",stdin);
freopen("kalanchoe.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
f[0][0]=ld=g[0][0]=1;
for(int i=1;i<=5000;++i)
for(int j=i;j<=5000;++j)
f[i][j]=((ll)f[i][j-1]*(i-1)+(ll)f[i-1][j-1]*(m+1-i))%p,
g[i][j]=((ll)g[i][j-1]*(i-1)+(ll)g[i-1][j-1]*i)%p;
for(int i=1;i<=n;++i,ld=dp[0],dp[0]=0)
for(int j=1;j<=a[i]&&j<=m;++j)
(dp[0]+=(dp[j]=((ll)ld*f[j][a[i]]-(j<=a[i-1])*(ll)dp[j]*g[j][a[i]])%p))%=p;
printf("%d\n",((ll)ld+p)%p);
}
//s[i]=Σdp[i][j]*C[m][j];
0 条评论