题目
题目大意
有(K)种颜色的小球，每种颜色的小球有(c_i)个。
求相邻颜色不同的排列的方案数。
(Kleq 15)且(c_ileq 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_{1leq kleq i}{c_k})
枚举插空的位置个数(x)和插在相邻相等位置之间的个数(y)。
转移：(f_{i,j}*C_{sum+1-j}^{x-y}*C_j^y o f_{i+1,j-y+c_{i+1}-x})
感觉我的方法简单多了
代码（正解1）
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cassert>
#define mo 1000000007
inline 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<int,int> 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
",ans);
}
return 0;
}
总结
排列组合一类的DP，可以试着一层层插空。