bzoj3139 [Hnoi2013]比赛

Description

沫沫非常喜欢看足球赛，但因为沉迷于射箭游戏，错过了最近的一次足球联赛。此次联赛共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
但沫沫发现当球队较多时，计算工作量将非常大，所以这个任务就交给你了。请你计算出可能的比赛过程的数目，由于答案可能很大，你只需要输出答案对109+7取模的结果

Input

第一行是一个正整数N，表示一共有N支球队。接下来一行N个非负整数，依次表示各队的最后总得分。

输入保证20%的数据满足N≤4，40%的数据满足N≤6，60%的数据满足N≤8，100%的数据满足3≤N≤10且至少存在一组解。

Output

仅包含一个整数，表示答案对10^9+7取模的结果

Sample Input

4
4 3 6 4

Sample Output

正解：记忆化搜索+$hash$。

这题纯爆搜有50分，和最优性剪枝的一样。。

然后考虑优化吧。。这个优化太鬼畜了，看题解都看了好久。。

我们可以设f[i][s]表示i+1-n之间已经打完了比赛，分数的状态。然后我们直接状压一下分数，枚举每个人，记忆化搜索就行。

但是为什么这题能够状压呢，我们可以发现，每个人最多只有27分。我们把状态数弄成29进制的，我们可以发现，状态数最大都只有$29^{10}$，不会爆$long long$，然后我们直接开$map$存状态就好了。

还有一点，我们可以将原数组从小到大排序，然后直接每次用前面的人和后面的人先匹配就行了。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <complex>
 5 #include <cstring>
 6 #include <cstdlib>
 7 #include <cstdio>
 8 #include <vector>
 9 #include <cmath>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #define rhl (1000000007)
15 #define inf (1<<30)
16 #define il inline
17 #define RG register
18 #define ll long long
19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
20 
21 using namespace std;
22 
23 map <ll,int> mp[12],use[12];
24 
25 int a[12],n;
26 
27 il int gi(){
28     RG int x=0,q=1; RG char ch=getchar();
29     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
30     if (ch=='-') q=-1,ch=getchar();
31     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
32     return q*x;
33 }
34 
35 il ll gethash(int *val){
36     RG ll tot=0;
37     for (RG int i=1;i<=n;++i)
38     tot=tot*29+val[i];
39     return tot;
40 }
41 
42 il int dfs(int *val,RG int l,RG int r){
43     if (l>=r){
44     if (val[l]) return 0;
45     if (l==n) return 1; int b[12];
46     for (RG int i=1;i<=n;++i) b[i]=val[i];
47     sort(b+l+1,b+n+1); //后面的分数排序是不会对前面造成影响的
48     RG ll s=gethash(b); //29进制hash
49     if (use[l+1][s]) return mp[l+1][s];
50     RG int tot=dfs(b,l+1,n); mp[l+1][s]=tot;
51     use[l+1][s]=1; return tot; //要用use数组记录每个状态是否搜过
52     }
53     if (3*(r-l)<val[l]) return 0; //可行性剪枝
54     RG ll tot=0;
55     if (val[l] && val[r]){
56     val[l]--,val[r]--;
57     tot+=dfs(val,l,r-1);
58     val[l]++,val[r]++;
59     }
60     if (val[l]>=3){
61     val[l]-=3;
62     tot+=dfs(val,l,r-1);
63     val[l]+=3;
64     }
65     if (val[r]>=3){
66     val[r]-=3;
67     tot+=dfs(val,l,r-1);
68     val[r]+=3;
69     }
70     return (int)(tot%rhl);
71 }
72 
73 il void work(){
74     n=gi(); for (RG int i=1;i<=n;++i) a[i]=gi();
75     sort(a+1,a+n+1); printf("%d
",dfs(a,1,n));
76     return;
77 }
78 
79 int main(){
80     File("match");
81     work();
82     return 0;
83 }