题目大意

有\(K\)种颜色的小球，每种颜色的小球有\(c_i\)个。

求相邻颜色不同的排列的方案数。

\(K\leq 15\)且\(c_i\leq 6\)

思考历程&正解1

我是一个智障，所以就先想到了一个智障方法。

首先考虑暴力。

暴力的时候记录上一个的颜色和每种颜色剩余的小球数量，转移的时候选择一种与上一个颜色不同的小球，将它的个数减一。

设状态\(f_{S,i}\)表示状态为\(S\)，最后一个小球颜色为\(i\)的方案数。

显然直接这样设状态会爆掉吧……

接着我们发现答案是与小球的顺序无关的，那我们可以考虑将组成一样的压起来。

建立一个桶，桶的下标范围是\([0,6]\)，表示小球的个数。桶中的每个元素表示的是小球的个数为下标的颜色个数。

显然，桶的每个元素加起来等于\(15\)（如果一开始\(K<15\)，就补\(0\)）

可以计算这个桶的方案数：

相当于将\(15\)个球放进\(7\)个箱子里，每个箱子可以为空：\(C_{15+7-1}^{7-1}=54264\)

可以存下。

这个桶可以用个\(7\)位的\(16\)进制数来存，不会超过int。用\(map\)给每个桶分配一个下标。

然后\(i\)的定义也要变一下，表示最后一个小球的颜色的个数。范围在\([0,6]\)，显然不会炸。

由于多组数据，所以考虑反着转移。\(f_{S,i}\)中的\(S\)表示的状态是已经放了的状态（不是剩余的状态）。

转移的时候枚举\(j\)。设桶下标为\(j\)的数是\(k\)，如果\(i=j\)，由于不能重复，所以乘上\(k-1\)。否则直接乘\(k\)。

这些是预处理的部分。对于每个询问，由于它按照一定顺序排列，所以要除以排列数。排列数有个公式：\(\frac{(\sum{c_i})!}{\prod {c_i!}}\)（不会证明……）

正解2

DYP的高级解法。

设\(f_{i,j}\)表示做到第\(i\)个颜色，相邻相等的个数为\(j\)。

按照颜色一层一层转移，每次转移的时候插空。

现在由\(f_{i,j}\)往后面的转移，设\(sum=\sum_{1\leq k\leq i}{c_k}\)

枚举插空的位置个数\(x\)和插在相邻相等位置之间的个数\(y\)。

转移：\(f_{i,j}*C_{sum+1-j}^{x-y}*C_j^y\to f_{i+1,j-y+c_{i+1}-x}\)

~~感觉我的方法简单多了~~

代码（正解1）

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       #include 
        
         #define mo 1000000007inline int my_pow(int x,int y){    int res=1;    for (;y;y>>=1,x=1ll*x*x%mo)        if (y&1)            res=1ll*res*x%mo;    return res;}int pow16[8],fac[16];int cnt;map
         
           h;int f[200000][7];int q[200000];inline void init(){ h[15]=++cnt; f[cnt][6]=1; int head=0,tail=1; q[1]=15; do{ int x=q[++head],s=h[x]; for (int j=0;j<6;++j){ int k=x/pow16[j]%16; if (k){ int y=x-pow16[j]+pow16[j+1]; int *p=&h[y]; if (*p==0){ *p=++cnt; q[++tail]=y; } for (int i=1;i<=6;++i) (f[*p][j+1]+=1ll*f[s][i]*(i!=j?k:k-1)%mo)%=mo; } } } while (head!=tail);}int main(){ pow16[0]=1; for (int i=1;i<=7;++i) pow16[i]=pow16[i-1]*16; fac[0]=1; for (int i=1;i<=15;++i) fac[i]=1ll*fac[i-1]*i%mo; init(); int T; scanf("%d",&T); while (T--){ int K; scanf("%d",&K); int x=15-K; for (int i=1;i<=K;++i){ int c; scanf("%d",&c); x+=pow16[c]; } int s=h[x]; long long ans=0; for (int i=1;i<=6;++i) ans+=f[s][i]; ans%=mo; for (int i=0;i<=6;++i) ans=1ll*ans*fac[x/pow16[i]%16]%mo; ans=1ll*ans*my_pow(fac[15],mo-2)%mo; printf("%lld\n",ans); } return 0;}

总结

排列组合一类的DP，可以试着一层层插空。

转载于:https://www.cnblogs.com/jz-597/p/11283523.html

你可能感兴趣的文章