沫沫非常喜欢看足球赛，但因为沉迷于射箭游戏，错过了最近的一次足球联赛。此次联 赛共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取模的结果
第一行是一个正整数N，表示一共有N支球队。接下来一行N个非负整数，依次表示各队的最后总得分。
输入保证20%的数据满足N≤4，40%的数据满足N≤6，60%的数据满足N≤8，100%的数据满足3≤N≤10且至少存在一组解。
仅包含一个整数，表示答案对10^9+7取模的结果
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define maxn 12 7 #define mod 1000000007 8 #define base1 31 9 #define mod1 99997 10 #define base2 97 11 #define mod2 480881 12 #define maxnode 1000000 13 using namespace std; 14 char ch; 15 bool ok; 16 void read(int &x){ 17 for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch==‘-‘) ok=1; 18 for (x=0;isdigit(ch);x=x*10+ch-‘0‘,ch=getchar()); 19 if (ok) x=-x; 20 } 21 int n,list[maxn]; 22 struct state{ 23 int tot,hash[mod1],pre[maxnode],key[maxnode],ans[maxnode]; 24 int find(int st,int n){ 25 int u=st,v=st; 26 for (int i=1;i<=n;i++) u=(u*base1+list[i]+1)%mod1; 27 for (int i=1;i<=n;i++) v=(v*base2+list[i]+1)%mod2; 28 for (int p=hash[u];p;p=pre[p]) if (key[p]==v) return ans[p]; 29 return -1; 30 } 31 void add(int st,int n,int tmp){ 32 int u=st,v=st; 33 for (int i=1;i<=n;i++) u=(u*base1+list[i]+1)%mod1; 34 for (int i=1;i<=n;i++) v=(v*base2+list[i]+1)%mod2; 35 pre[++tot]=hash[u],hash[u]=tot,key[tot]=v,ans[tot]=tmp; 36 } 37 }S; 38 int dfs(int st,int n){ 39 if (n==1&&!list[n]) return 1; 40 if (n==1&&list[n]) return 0; 41 if (st==n&&list[n]) return 0; 42 if (st==n&&!list[n]) return dfs(1,n-1); 43 if (st==1){ 44 int sum=0; 45 for (int i=1;i<=n;i++) sum+=list[i]; 46 if (sum<n*(n-1)||sum>3*n*(n-1)/2) return 0; 47 } 48 if (st==1) sort(list+1,list+n+1); 49 int ans; 50 if (st==1){ 51 ans=S.find(st,n); 52 if (ans!=-1) return ans; 53 } 54 int res[maxn]; 55 if (!list[n]){ 56 for (int i=st;i<n;i++) if (list[i]<3) return 0; 57 for (int i=1;i<=n;i++) res[i]=list[i]; 58 for (int i=st;i<n;i++) list[i]-=3; 59 ans=dfs(1,n-1); 60 for (int i=1;i<=n;i++) list[i]=res[i]; 61 if (st==1) S.add(st,n,ans); 62 return ans; 63 } 64 for (int i=1;i<=n;i++) res[i]=list[i]; 65 ans=0; 66 if (list[n]-1<=(n-st-1)*3&&list[st]>=1&&list[n]>=1) list[n]--,list[st]--,ans+=dfs(st+1,n),ans%=mod; 67 for (int i=1;i<=n;i++) list[i]=res[i]; 68 if (list[n]>=3) list[n]-=3,ans+=dfs(st+1,n),ans%=mod; 69 for (int i=1;i<=n;i++) list[i]=res[i]; 70 if (list[n]<=(n-st-1)*3&&list[st]>=3) list[st]-=3,ans+=dfs(st+1,n),ans%=mod; 71 for (int i=1;i<=n;i++) list[i]=res[i]; 72 if (st==1) S.add(st,n,ans); 73 return ans; 74 } 75 int main(){ 76 read(n); 77 for (int i=1;i<=n;i++) read(list[i]); 78 printf("%d\n",dfs(1,n)); 79 return 0; 80 }
原文：http://www.cnblogs.com/chenyushuo/p/5083257.html