着色方案（bzoj 1079）

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

HINT

100%的数据满足：1 <= k <= 15, 1 <= ci <= 5

/*

    直接状态压缩是显然是不可行的，我们考虑如果没有相邻颜色不相同的限制的话，

    如果两种油漆能染的木块数目相同，我们就可以认为两种油漆无差别。

    设dp[a1][a2][a3][a4][a5]为能染1个木块的油漆有a1种……的方案数。

    但是有相邻颜色的限制，如果上一次用了颜色数为last的油漆，

    那么这一次有一种颜色数为last-1的油漆就不能用了，转移的时候注意一下。

*/

#include<iostream>

#include<cstdio>

#define mod 1000000007

#define lon long long

using namespace std;

int s[],dp[][][][][][],k;

int dfs(int a1,int a2,int a3,int a4,int a5,int last){

    if(dp[a1][a2][a3][a4][a5][last]) return dp[a1][a2][a3][a4][a5][last];

    if(a1+a2+a3+a4+a5==) return dp[a1][a2][a3][a4][a5][last]=;

    lon tot=;

    if(a1) tot+=1LL*(a1-(last==))*dfs(a1-,a2,a3,a4,a5,),tot%=mod;

    if(a2) tot+=1LL*(a2-(last==))*dfs(a1+,a2-,a3,a4,a5,),tot%=mod;

    if(a3) tot+=1LL*(a3-(last==))*dfs(a1,a2+,a3-,a4,a5,),tot%=mod;

    if(a4) tot+=1LL*(a4-(last==))*dfs(a1,a2,a3+,a4-,a5,),tot%=mod;

    if(a5) tot+=1LL*a5*dfs(a1,a2,a3,a4+,a5-,),tot%=mod;

    return dp[a1][a2][a3][a4][a5][last]=tot;

}

int main(){

    scanf("%d",&k);

    for(int i=;i<=k;i++){

        int x;scanf("%d",&x);

        s[x]++;

    }

    printf("%d",dfs(s[],s[],s[],s[],s[],));

    return ;

}

巴特西