记录编号	23220	评测结果	AAAAAAAAAA
题目名称	[SCOI 2008] 着色方案	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.162 s
提交时间	2011-03-03 10:00:41	内存使用	11.71 MiB

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

struct node
{
	long long f;
	int num[6],k;
	node *next;
	node()
	{
		f=-1;
		next=NULL;
	}
}hash[200001],lian[100001];
int lh;

int MOD(long long x)
{
	x%=1000000007;
	return x;
}

void add(node *&p,int *n,int k,long long f)
{
	if (!p)
	{
		p=&lian[++lh];
		for (int i=1;i<=5;i++) p->num[i]=n[i];
		p->k=k;
		p->f=MOD(f);
	}
	else
	{
		for (int i=1;i<=5;i++) if (p->num[i]!=n[i])
		{
			add(p->next,n,k,f);
			return ;
		}
		if (p->k!=k) {add(p->next,n,k,f);return ;}
		p->f = MOD((long long)p->f + f);
	}
}

void addd(node *p,int *n,int k,long long f)
{
	for (int i=1;i<=5;i++) if (p->num[i]!=n[i])
	{
		add(p->next,n,k,f);
		return ;
	}
	if (p->k!=k) {add(p->next,n,k,f);return ;}
	p->f = MOD((long long)p->f + f);
}

int has(int *n,int k)
{
	int hn=0;
	for (int i=1;i<=5;i++) hn=(17*hn+n[i]) % 199991;
	hn=(17*hn+k) % 199991;
	return hn;
}

void newnode(int *n,int k,long long f)
{
	int hn=has(n,k);
	
	if (hash[hn].f==-1)
	{
		for (int i=1;i<=5;i++) hash[hn].num[i]=n[i];
		hash[hn].k=k;
		hash[hn].f=MOD(f);
	}
	else addd(hash+hn,n,k,f);
}

node *find(node *p,int *n,int k)
{
	if (!p) return NULL;
	else
	{
		for (int i=1;i<=5;i++) if (p->num[i]!=n[i]) return find(p->next,n,k);
		if (p->k!=k) return find(p->next,n,k);
		return p;
	}
}

int c[16],K,num[6],t[6];
void dp()
{
	newnode(num,0,1);
	int n[6];
	for (int T=K;T>=0;T--)
	for (n[5]=min(T,num[5]);n[5]>=0;n[5]--)
	for (n[4]=min(T,num[4]+num[5]-n[5]);n[4]>=0;n[4]--)
	for (n[3]=min(T,num[3]+num[5]-n[5]+num[4]-n[4]);n[3]>=0;n[3]--)
	for (n[2]=min(T,num[2]+num[5]-n[5]+num[4]-n[4]+num[3]-n[3]);n[2]>=0;n[2]--)
	{
		n[1]=T-n[5]-n[4]-n[3]-n[2];
		if (n[1]<0) continue;
		for (int lastc=0;lastc<=5;lastc++)
		if (find(hash+has(n,lastc),n,lastc)!=NULL)
		for (int newc=1;newc<=5;newc++) if (n[newc]>0)
		{
			node *p=find(hash+has(n,lastc),n,lastc);
			if (newc!=lastc)
			{
				for (int i=1;i<=5;i++) t[i]=n[i];
				t[newc-1]++;t[newc]--;
				newnode(t,newc-1,p->f*n[newc]);
			}
			else
			{
				for (int i=1;i<=5;i++) t[i]=n[i];
				t[newc-1]++;t[newc]--;
				newnode(t,newc-1,p->f*(n[newc]<1 ? 0 : n[newc]-1));
			}
		}
	}
}

int main()
{
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	scanf("%d",&K);
	for (int i=1;i<=K;i++) 
	{	
		scanf("%d",c+i);
		++num[c[i]];
	}
	dp();
	for (int i=1;i<=5;i++) num[i]=0;
	node *p=find(hash,num,0);
	cout<<((p->f < 0) ? 0 : p->f )<<"\n";
	return 0;
}