相邻色块不同的着色方案，似乎这道题已经见过3个版本了。
Description
有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。
Input
第一行为一个正整数k，第二行包含k个整数c1, c2, ... , ck。
Output
输出一个整数，即方案总数模1,000,000,007的结果。
Sample Input
3
1 2 3
Sample Output
10
HINT
1 <= k <= 15,，1 <= ci <= 5。
Solution
k和ci都这么小，状压肯定没跑了。
如果你把k和ci的数据范围换一换，你应该会很容易地设计出状态吧。
我们先试着从5^15的状态表示法入手，看看有什么可改进的地方。
你会发现有很多状态本质上是一样的，颜色之间其实是没有区别的。
例如七种颜色的数量{1,4,3,2,2,1,2}和{1,2,3,2,4,2,1}排序后都是{1,1,2,2,2,3,4}。
所以我们就试着把状态压一压，状态表示为当前每种数量的颜色有多少种。
这样就状态又变成15^5啦，科学得不要不要的。
具体状态为f[i][j][k]表示已经涂了i格，状态为j，最后一格涂的是在当前状态中数量为k的颜色，转移自己看着办吧。
时间复杂度O(n*k^ci*ci^2)，记忆化搜索似乎会省掉那个n？（n=Σci）
#include <cstdio> #include <cstring> #include <algorithm> #define MN 1100005 #define mod 1000000007 using namespace std; int m,n,S; int g[6],ys[6],f[2][MN][6],q[2][MN],tp[2]; bool u[MN]; inline int read() { int n=0,f=1; char c=getchar(); while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();} while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();} return n*f; } inline void rw(int &x,int y) {x+=y; if (x>=mod) x-=mod;} int main() { register int x,i,j,k,l,lg,rg,gs; for (m=read();m--;) ++g[x=read()],n+=x; for (ys[1]=1,i=2;i<=5;++i) ys[i]=ys[i-1]<<4; for (i=1;i<=5;++i) S+=g[i]*ys[i]; for (f[0][q[0][tp[0]=1]=S][0]=1,lg=0,rg=1,i=0;i<n;++i,swap(lg,rg)) { tp[rg]=0; for (j=1;j<=tp[lg];++j) if (!u[q[lg][j]]) for (u[q[lg][j]]=true,k=0;k<5;f[lg][q[lg][j]][k++]=0) if (f[lg][q[lg][j]][k]) for (x=q[lg][j],l=5;l;x%=ys[l--]) if (gs=x/ys[l]) if (k!=l) rw(f[rg][q[lg][j]-ys[l]+ys[l-1]][l-1],1LL*f[lg][q[lg][j]][k]*gs%mod), q[rg][++tp[rg]]=q[lg][j]-ys[l]+ys[l-1]; else if (gs>1) rw(f[rg][q[lg][j]-ys[l]+ys[l-1]][l-1],1LL*f[lg][q[lg][j]][k]*(gs-1)%mod), q[rg][++tp[rg]]=q[lg][j]-ys[l]+ys[l-1]; for (j=1;j<=tp[lg];++j) u[q[lg][j]]=false; } printf("%d",f[lg][0][0]); }
Last Word
世界上还有比恶意散播题解的更毒的人吗？