[SCOI2008]着色方案

Time Limit:10000MS  Memory Limit:165536K
Total Submit:20 Accepted:16
Case Time Limit:1000MS

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

【样例2】
Input
5
2 2 2 2 2
Output
39480
【样例3】
Input
10
1 1 2 2 3 3 4 4 5 5
Output
85937576
数据规模】
50%的数据满足：1 <= k <= 5, 1 <= ci <= 3
100%的数据满足：1 <= k <= 15, 1 <= ci <= 5

Source
这题一看就知道是要Dp的，而且状态很麻烦，好在c最大只有5，所以可以用一个6维数组表示
，就是第i个表示当前还有i个的颜色还有几个，还要一个Last表示最后一个是哪个颜色。然后用
Hash表存储状态就可以了。。unsigned long long中的-1就是最大值。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,c=6,seed=17,mod=1000000007,size=17771;
typedef unsigned long long ull;
int n;
struct State
{
int Num,Last;
State(){memset(Num,0,sizeof(Num));}
ull HashCode() const
{
ull ret=0;
rep(i,c) ret*=seed,ret+=Num[i];
ret*=seed;return ret+=Last;
}
State Next()
{
State s=*this;
s.Num[Last]–;s.Num[Last-1]++;return s;
}
bool Legal(){return Num[Last]>0&&Last>0;}
void operator=(const State&o)
{
memcpy(Num,o.Num,sizeof(Num));
Last=o.Last;
}
};
struct Hash
{
struct Node
{
ull key,Count;
Node*next;
Node(ull _key,Node*_next):key(_key),next(_next),Count(-1){}
}*H[size];
Hash(){memset(H,0,sizeof(H));}
ull& Find(const State&a)
{
ull code=a.HashCode(),h=code%size;
for(Node*i=H[h];i;i=i->next)if(i->key==code) return i->Count;
return H[h]=new Node(code,H[h]),H[h]->Count;
}
}H;
ull dfs(State S,int Left)
{
ull&x=H.Find(S);if(x!=-1) return x;
if(!S.Legal()) return x=0;
if(Left==1) return x=1;
x=0;
State NewS=S.Next();
for(int i=1;i<c;i++)
{
NewS.Last=i;
if(i!=S.Last&&S.Num[i])
{
x+=S.Num[i]*dfs(NewS,Left-1);
x%=mod;
}
if(i==S.Last&&S.Num[i]>1)
{
x+=(S.Num[i]-1)*dfs(NewS,Left-1);
x%=mod;
}
}
return x;
}
int main()
{
//freopen("in","r",stdin);
State now;ull ans=0;
int n,x,s=0;cin>>n;rep(i,n) cin>>x,now.Num[x]++,s+=x;
rep(i,c) now.Last=i,ans+=now.Num[i]*dfs(now,s),ans%=mod;
cout<<ans<<endl;
}