$ \color{#0066ff}{ 题目描述 }$
沫沫非常喜欢看足球赛，但因为沉迷于射箭游戏，错过了最近的一次足球联赛。此次联 赛共N支球队参加，比赛规则如下：
(1) 每两支球队之间踢一场比赛。 (2) 若平局，两支球队各得1分。
(3) 否则胜利的球队得3分，败者不得分。 尽管非常遗憾没有观赏到精彩的比赛，但沫沫通过新闻知道了每只球队的最后总得分， 然后聪明的她想计算出有多少种可能的比赛过程。
譬如有3支球队，每支球队最后均积3分，那么有两种可能的情况：
可能性1 可能性2
球队 A B C 得分 球队 A B C 得分
A - 3 0 3 A - 0 3 3
B 0 - 3 3 B 3 - 0 3
C 3 0 - 3 C 0 3 - 3
但沫沫发现当球队较多时，计算工作量将非常大，所以这个任务就交给你了。请你计算 出可能的比赛过程的数目，由于答案可能很大，你只需要输出答案对\(10^9+7\)取模的结果
\(\color{#0066ff}{输入格式}\)
第一行是一个正整数N，表示一共有N支球队。 接下来一行N个非负整数，依次表示各队的最后总得分。
\(\color{#0066ff}{输出格式}\)
仅包含一个整数，表示答案对10^9+7取模的结果
\(\color{#0066ff}{输入样例}\)
4
4 3 6 4
\(\color{#0066ff}{输出样例}\)
3
\(\color{#0066ff}{数据范围与提示}\)
输入保证
20%的数据满足N<=4，
40%的数据满足N<=6，
60%的数据满足N<=8，
100%的数据 满足3<=N<=10且至少存在一组解。
\(\color{#0066ff}{题解}\)
一看n这么小，先想爆搜吧
肯定是搜索共\(\frac{n*(n-1)}{2}\)场比赛的情况，然后判断是否合法
然后开始剪枝qwq
1、到最后统计答案的时候，肯定要判断合不合法，不如搜索的时候就判断是否超过分数上限
2、对于当前的人，如果他赢了接下来所有的比赛都拿不到该有的分，就剪掉
3、这是一个很强的剪枝，我们设赢的场次为x，输的场次为y，那么显然\(x+y=\frac{n*(n-1)}{2},3x+2y=\sum a_i\)
然后我们就可以解出x和y，从而剪掉大量的分支！
4、 记忆化！
如果人数确定，每个人得分确定，那么答案唯一
所以对于剩下人的方案，可以记忆化一下，把每个人的得分hash一下存起来
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int mod = 1e9 + 7;
std::map<LL, LL> mp;
int n, ans;
int a[20], ls[20], win, orz, b[20];
int dfs(int x, int y) {
if(x == n) return 1;
if(ls[x] + 3 * (n - y + 1) < a[x]) return 0;
LL tot = 0;
if(y > n) {
for(int i = x + 1; i <= n; i++) b[i] = a[i] - ls[i];
std::sort(b + x + 1, b + n + 1, std::greater<int>());
LL zt = 0;
for(int i = x + 1; i <= n; i++) zt = zt * 28LL + b[i];
if(mp.find(zt) != mp.end()) return mp[zt];
else return mp[zt] = dfs(x + 1, x + 2);
}
if(ls[x] + 3 <= a[x] && win) {
ls[x] += 3, win--;
tot += dfs(x, y + 1);
ls[x] -= 3, win++;
}
if(ls[y] + 3 <= a[y] && win) {
ls[y] += 3, win--;
tot += dfs(x, y + 1);
ls[y] -= 3, win++;
}
if(ls[x] + 1 <= a[x] && ls[y] + 1 <= a[y] && orz) {
ls[x]++, ls[y]++, orz--;
tot += dfs(x, y + 1);
ls[x]--, ls[y]--, orz++;
}
return tot;
}
int main() {
n = in();
for(int i = 1; i <= n; i++) win += (a[i] = in());
win -= n * (n - 1);
orz = (n * (n - 1) >> 1) - win;
std::sort(a + 1, a + n + 1, std::greater<int>());
printf("%d", dfs(1, 2) % mod);
return 0;
}