Description

沫沫非常喜欢看足球赛, 但因为沉迷于射箭游戏, 错过了最近的一次足球联赛. 此次联赛共 \(n\) 支球队参加, 比赛规则如下:

  1. 每两支球队之间踢一场比赛.
  2. 若平局, 两支球队各得 1 分.
  3. 否则胜利的球队得 3 分, 败者不得分.

尽管非常遗憾没有观赏到精彩的比赛, 但沫沫通过新闻知道了每只球队的最后总得分, 然后 聪明的她想计算出有多少种可能的比赛过程.

譬如有 3 支球队, 每支球队最后均积 3 分, 那么有两种可能的情况:

可能性 1:

球队 A B C 得分
A \(-\) \(3\) \(0\) \(3\)
B \(0\) \(-\) \(3\) \(3\)
C \(3\) \(0\) \(-\) \(3\)

可能性 2:

球队 A B C 得分
A \(-\) \(0\) \(3\) \(3\)
B \(3\) \(-\) \(0\) \(3\)
C \(0\) \(3\) \(-\) \(3\)

但沫沫发现当球队较多时, 计算工作量将非常大, 所以这个任务就交给你了. 请你计算出可能的比赛过程的数目, 由于答案可能很大, 你只需要输出答案对 \(10^9+7\) 取模的结果.

Input

第一行是一个正整数 \(n\), 表示一共有 \(n\) 支球队.

接下来一行 \(n\) 个非负整数, 依次表示各队的最后总得分.

Output

仅包含一个整数, 表示答案对 \(10^9+7\) 取模的结果.

Sample Input

4
4 3 6 4

Sample Output

3

Data Range

对于 20% 的数据, 满足:\(n \leq 4\);

对于 40% 的数据, 满足:\(n \leq 6\);

对于 60% 的数据, 满足:\(n \leq 8\);

对于 100% 的数据, 满足:\(3 \leq n \leq 10\), 并且至少存在一组解.

Explanation

首先看到这道题数据范围很小就可以猜出来要么是插头 DP, 要么是状态压缩 DP, 要么就是 裸的暴力搜索...... 很显然这道题是暴力搜索.

针对 60% 数据的做法就是直接上暴搜, 不做任何优化, 所以说前面两个是送分的, 完全是闹着玩的.

然后对于 100% 的优化就是记忆化搜索, 用一个哈希函数来保存每一个状态对应的求值, 这有点像有限状态自动机. 用一个 STL map 来维护是最好不过的方法了.

关于暴搜的细节部分, 其实就不用多说了. 做法应该和 NOIP2015 斗地主有点类似, 但是关键的部分被转变为关于比分的修改了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <algorithm>

using namespace std;
typedef long long lli;
const int magic = 28;
const lli modr = 1000000007ll;
inline bool cmp(int a, int b) {
    return a > b; }

class state
{
public:
    int a[12];
    inline lli hash(void)
    {
        lli res = 0;
        for (int i = 0; i <= this->a[0]; i++)
            res = res * magic + a[i];
        return res;
    }
};

map<lli, int> hsh_map;

int dfs(int depth, state st)
{
    int sz = st.a[0];
    if (sz == 1) {
        return 0;
    } else if (st.a[sz] > depth * 3) {
        return 0;
    } else if (depth < 1) {
        sort(st.a + 1, st.a + sz + 1, cmp);
        st.a[0] -= 1;
        lli hsh = st.hash();
        if (hsh_map.find(hsh) != hsh_map.end())
            return hsh_map[hsh];
        int n_res = dfs(st.a[0] - 1, st);
        hsh_map[hsh] = n_res;
        return n_res;
    }
    // Done talking about terminus situations
    int res = 0;
    if (st.a[sz] >= 3) {
        st.a[sz] -= 3;
        res += dfs(depth - 1, st);
        st.a[sz] += 3;
    }
    if (st.a[sz] >= 1 && st.a[depth] >= 1) {
        st.a[sz] -= 1, st.a[depth] -= 1;
        res += dfs(depth - 1, st);
        st.a[sz] += 1, st.a[depth] += 1;
    }
    if (st.a[depth] >= 3) {
        st.a[depth] -= 3;
        res += dfs(depth - 1, st);
        st.a[depth] += 3;
    }
    // Terminus of this depth first search
    if (depth == sz - 1)
        hsh_map[st.hash()] = res;
    return res;
}

int n;
state sto;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &sto.a[++sto.a[0]]);
    sort(sto.a + 1, sto.a + n + 1, cmp);
    hsh_map[28] = 1;
    int res = dfs(n - 1, sto);
    printf("%d\n", res);
    return 0;
}