C++14(g++5.4) 解法, 执行用时: 8ms, 内存消耗: 5112K, 提交时间: 2020-07-17 19:24:58

#include<bits/stdc++.h>
using namespace std;

const int maxk=16;
const int mod=1e9+7;
#define ll long long
ll dp[maxk][maxk][maxk][maxk][maxk][6];

ll dfs(int a,int b,int c,int d,int e,int last){
    if(dp[a][b][c][d][e][last]||a+b+c+d+e==0){
        return dp[a][b][c][d][e][last];
    }
    ll res=0;
    if(a) res=(res+(a-(last==1?1:0))*dfs(a-1,b,c,d,e,0)%mod)%mod;
    if(b) res=(res+(b-(last==2?1:0))*dfs(a+1,b-1,c,d,e,1)%mod)%mod;
    if(c) res=(res+(c-(last==3?1:0))*dfs(a,b+1,c-1,d,e,2)%mod)%mod;
    if(d) res=(res+(d-(last==4?1:0))*dfs(a,b,c+1,d-1,e,3)%mod)%mod;
    if(e) res=(res+e*dfs(a,b,c,d+1,e-1,4)%mod)%mod;
    return dp[a][b][c][d][e][last]=res;
}

int main(){
    int k,c,cnt[maxk]={0};
    cin>>k;
    for(int i=1;i<=k;i++){
        cin>>c;
        cnt[c]++;
    }
    dp[0][0][0][0][0][0]=1;
    cout<<dfs(cnt[1],cnt[2],cnt[3],cnt[4],cnt[5],0)%mod<<endl;
}

C++ 解法, 执行用时: 12ms, 内存消耗: 5372K, 提交时间: 2021-06-09 11:28:51

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
int DP[16][16][16][16][16][6]={0};
long long DFS(int a,int b,int c,int d,int e,int s)
{
	if(DP[a][b][c][d][e][s])return DP[a][b][c][d][e][s];
	int ans=0;
	if(a)ans=(ans+(a-(s==2))*DFS(a-1,b,c,d,e,1))%mod;
	if(b)ans=(ans+(b-(s==3))*DFS(a+1,b-1,c,d,e,2))%mod;
	if(c)ans=(ans+(c-(s==4))*DFS(a,b+1,c-1,d,e,3))%mod;
	if(d)ans=(ans+(d-(s==5))*DFS(a,b,c+1,d-1,e,4))%mod;
	if(e)ans=(ans+e*DFS(a,b,c,d+1,e-1,5))%mod;
	return DP[a][b][c][d][e][s]=ans;
}
int main()
{
    int i,n,x,a[9]={0};
	scanf("%d",&n);
	while(n--)scanf("%d",&x),a[x]++;
	for(i=1;i<=5;i++)DP[0][0][0][0][0][i]=1;
	printf("%d\n",DFS(a[1],a[2],a[3],a[4],a[5],0));
    return 0;
}