长寿花：dp

当然可以打组合数+CRT什么的，但是其实不必那么麻烦。

先讲那个思路，再转化过来吧。

首先可以发现的一个问题：所有颜色之间是没有区别的，所以我们其实并不在意到底是哪几种，我们只需要知道有几种就可以了。

逐层递推：设dp[i][j]表示到了第i层，这层用了某j种颜色的总方案数。

注意这里为了方便去重，所以dp的含义里是已经确定了j种颜色，所以不要乘上 $ C_m^j $

那么再设s[i]是填到第i曾为止的总方案数那么s[i]=Σ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。

所以整体思路还是比较简单的。并没有调出我的CRT所以不粘这个代码。

然后想一想简化：当模数不是质数时除法会出问题而加减乘都没事。然而整个代码里只有组合数那一步需要除法。

那么怎么搞掉组合数呢？

需要一些脑洞，我们新开一个数组f。f表示的和g数组差不多，但是是已经钦定了具体是哪j种颜色。

所以g的转移就是f[i][j]=f[i-1][j-1]*(m+1-j)+f[i-1][j]*(j-1);

如果不新增颜色的话那么和f是一样的转移，但是如果是新增了颜色，因为颜色需要确定，所以我们需要明确知道新加入的是哪种颜色。

那就是在还没有被选过的颜色里选一个，一共m种已经用了j-1种，那么剩余的选择就是m-j+1。

那么dp的含义也随之变化，dp亦表示已钦定后的值，那么就相当与乘上那个组合数了。

再考虑dp转移。dp[i][j]=s[i-1]*f[j][a[i]]-dp[i-1][j]*g[j][a[i]];含义的话也类似。

在总方案里我们是已钦定的所以本层到底是哪几种不重要，所以乘f。

而在dp[i-1][j]里我们对于每一种方案里都已确定好颜色，每一个方案对应的本层都有特定的限制，所以需要钦定，用g乘。

代码短多了。时间也快了。

还有其实数组不用滚，用完直接覆盖就行。

 #include<cstdio>

 long long n,p,m,a[],f[][],dp[],g[][],ld;

 main(){

     scanf("%lld%lld%lld",&n,&m,&p);for(int i=;i<=n;++i)scanf("%lld",&a[i]);

     f[][]=ld=g[][]=;

     for(int i=;i<=;++i) for(int j=i;j<=;++j)

         f[i][j]=(f[i][j-]*(i-)+f[i-][j-]*(m+-i))%p,g[i][j]=(g[i][j-]*(i-)+g[i-][j-]*i)%p;

     for(int i=;i<=n;++i,ld=dp[],dp[]=) for(int j=;j<=a[i]&&j<=m;++j)

         (dp[]+=(dp[j]=(ld*f[j][a[i]]-(j<=a[i-])*dp[j]*g[j][a[i]])%p))%=p;

     printf("%lld\n",(ld+p)%p);

 }

516B

巴特西

长寿花：dp

最新文章

热门文章