C++14(g++5.4) 解法, 执行用时: 297ms, 内存消耗: 4344K, 提交时间: 2019-10-29 22:18:27

// luogu-judger-enable-o2
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <tr1/unordered_map>
#define re register
typedef long long ll;
using namespace std;
using namespace std::tr1;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10+10;
const int MOD=1e9+7;
const int BASE=28;

inline int cmp(const int x,const int y) { return x>y; }
inline void add(int& x,int y) { x+=y; if (x>=MOD) x-=MOD; }

int n,s[N],a[N],b[N];
unordered_map<ll,int> mem;
unordered_map<ll,int> vis;
int su,sx,sy;

inline int dfs(int u,int v) { //u VS v
    if (u==n) return 1;
    if (a[u]+3*(n-v+1)<s[u]) return 0;
    int rt=0;
    if (v>n) {
        for (re int i=u+1;i<=n;++i) b[i]=s[i]-a[i];
        sort(b+u+1,b+n+1);
        ll S=0;
        for (re int i=u+1;i<=n;++i) S=S*BASE+b[i];
        if (vis[S]) return mem[S];
        else return vis[S]=1,mem[S]=dfs(u+1,u+2);
    }
    if (a[u]+3<=s[u]&&sx)
        a[u]+=3,--sx,add(rt,dfs(u,v+1)),++sx,a[u]-=3;
    if (a[u]+1<=s[u]&&a[v]+1<=s[v]&&sy)
        ++a[u],++a[v],--sy,add(rt,dfs(u,v+1)),++sy,--a[v],--a[u];
    if (a[v]+3<=s[v]&&sx)
        a[v]+=3,--sx,add(rt,dfs(u,v+1)),++sx,a[v]-=3;
    return rt;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) s[i]=read(),su+=s[i];
    sx=su-n*n+n,sy=(su-sx*3)/2;
    sort(s+1,s+n+1,cmp);
    printf("%d\n",dfs(1,2));
    return 0;
}

C++ 解法, 执行用时: 137ms, 内存消耗: 2280K, 提交时间: 2021-10-06 18:25:00

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int maxn = 15, M = 30;
int a[maxn], b[maxn];
int n;
unordered_map<int, int>mp;
int Hash(int m) {
	int ans = m - 1;
	for (int i = 1; i < m; i++)
		ans = ans * M + b[i];
	return ans;
}
int dfs(int x, int y) {
	if (a[x] > 3 * (x - y)) return 0;
	if (x == y) {
		if (x == 1) return 1;
		for (int i = 1; i < x ; i++) b[i] = a[i];
		sort(b + 1, b + x);
		int h = Hash(x);
		return mp.count(h) ? mp[h] : mp[h] = dfs(x - 1, 1);
	}
	int ans = 0;
	if (a[x] >= 3) {
		a[x] -= 3;
		ans += dfs(x, y + 1);
		a[x] += 3;
	}
    if (a[y] >= 3) {
		a[y] -= 3;
		ans += dfs(x, y + 1);
		a[y] += 3;
	}
	if (a[x] && a[y]) {
		a[x]--, a[y]--;
		ans+=dfs(x, y + 1);
		a[x]++, a[y]++;
	}
	
	return ans;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	printf("%d\n", dfs(n, 1));
}