学步园

http://www.lydsy.com/JudgeOnline/problem.php?id=1079

看了范围以为是搜索，直到我发现了“即方案总数模1,000,000,007的结果。”

一类不容易想到状态的DP，和ZJOI？？？有点像，比那个简单就是了

看了题解的状态表示，我自己写了个dp，结果写错了。。。。。

我好弱啊啊啊啊啊啊啊啊啊

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int getint()
{
    int r=0,k=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
    for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
    return k*r;
}
/////////////////////////////////////////////////
#define mod 1000000007;
int n,k;
int c[6];
LL dp[16][16][16][16][16][6];//前i个 a,b,c,e,d 
/////////////////////////////////////////////////
LL DP(int a,int b,int c,int d,int e,int k)
{
	LL &ans=dp[a][b][c][d][e][k];
	if(~ans) return ans;
	if(a+b+c+d+e==0) return ans=1;
	ans=0;
	if(a) ans+=(a-(k==2))*DP(a-1,b,c,d,e,1);
	if(b) ans+=(b-(k==3))*DP(a+1,b-1,c,d,e,2);
	if(c) ans+=(c-(k==4))*DP(a,b+1,c-1,d,e,3);
	if(d) ans+=(d-(k==5))*DP(a,b,c+1,d-1,e,4);
	if(e) ans+=(e)*DP(a,b,c,d+1,e-1,5);
	return ans%=mod;
}
/////////////////////////////////////////////////
void input()
{
    k=getint();
    int x;
    rep(i,1,k) x=getint(),c[x]++;
}
void solve()
{
	MS(dp,-1);
	printf("%lld\n",DP(c[1],c[2],c[3],c[4],c[5],0));
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    input(),
    solve();
    return 0;
}