题目描述

有n个木块排成一行，从左到右依次编号为1~n。
你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。 所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。
相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。

输入描述:

第一行为一个正整数k，第二行包含k个整数c1, c2, ... , ck。

输出描述:

输出一个整数，即方案总数模1,000,000,007的结果

题解

一共有15种颜色，如果直接从颜色入手会比较麻烦，

我们考虑存储剩余能涂x个木块的油漆有多少种。

设置dp[a][b][c][d][e][last]为还剩a种可以涂1个块的油漆,还剩b种可以涂2个块的油漆，还剩c种可以涂3个块的油漆，还剩d种可以涂4个块的油漆，还剩e种可以涂5个块的油漆,以及上一次涂的油漆是可以涂last个块的。

首先，当前选什么样的颜色不重要，只需满足不相邻条件就可以。举个例子，假设你要选还可以涂3个块的颜色，只需让c或者c-1乘上dp[a][b+1][c-1][d][e][last]就行。

因为如果你选了还可以涂3个块的颜色，选完以后它就变成了还可以涂2个块的颜色，所以我们需要让b+1同时c-1。

除此之外，上次选了还可以涂4个块的颜色，如果这次要选还可以涂3个块的颜色，那就不能再选上次选过的颜色，此时就应该乘以c-1才可以。

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
const int mod=1e9+7;
int c[6];
ll dp[20][20][20][20][20][6];
ll dfs(int c1,int c2,int c3,int c4,int c5,int lst){

    if(dp[c1][c2][c3][c4][c5][lst])
        return dp[c1][c2][c3][c4][c5][lst];
    ll rst=0;
    if(c1) rst+=(c1-(lst==2))*dfs(c1-1,c2,c3,c4,c5,1);
    if(c2) rst+=(c2-(lst==3))*dfs(c1+1,c2-1,c3,c4,c5,2);
    if(c3) rst+=(c3-(lst==4))*dfs(c1,c2+1,c3-1,c4,c5,3);
    if(c4) rst+=(c4-(lst==5))*dfs(c1,c2,c3+1,c4-1,c5,4);
    if(c5) rst+=(c5)*dfs(c1,c2,c3,c4+1,c5-1,5);
    return dp[c1][c2][c3][c4][c5][lst]=rst%mod;
}
////////////////////////////////////////////////////////////////////////
int main(){
    int k=gn();
    repi(i,1,5) dp[0][0][0][0][0][i]=1;
    repi(i,1,k){
        int x=gn();
        ++c[x];
    }
    print(dfs(c[1],c[2],c[3],c[4],c[5],0));
    return 0;
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/