题解

思路分析

这是一道 记忆化搜索 + 状态压缩 + 剪枝 的计数问题。

问题建模

• $N$ 支球队两两比赛，每场比赛结果为：胜（3分）、平（1分）、负（0分）
• 给定每支球队的总分，求有多少种可能的比赛结果
• 答案对 $10^9 + 7$ 取模

核心思路

1. 比赛总分验证

首先验证总分是否合理：

• 总共 $\frac{n(n-1)}{2}$ 场比赛
• 如果全平局：总分 = $n(n-1)$
• 如果全分胜负：总分 = $3 \times \frac{n(n-1)}{2}$

设总分为 $S$，胜负场次为 $sx$，平局场次为 $sy$：

解得：

2. DFS 枚举比赛结果

按顺序枚举每场比赛 $(x, y)$（$x < y$）：

• 球队 $x$ 胜（$+3$ 分），球队 $y$ 负（$+0$ 分）
• 球队 $y$ 胜（$+3$ 分），球队 $x$ 负（$+0$ 分）
• 平局（各 $+1$ 分）

剪枝条件：

• 当前已分配分数不超过目标分数
• 剩余比赛能提供的最大分数足够

3. 记忆化优化

对于状态 $(x, \text{剩余分数})$，使用哈希表记忆化。

由于每支球队的剩余分数可能不同，将分数数组排序后哈希，避免重复计算。

算法步骤

1. 预处理：

   • 计算总分 $S$
   • 计算胜负场和平局场
   • 按分数降序排序

2. DFS 枚举：

   • 枚举每场比赛的结果（3种）
   • 检查是否超过目标分数
   • 递归处理下一场比赛

3. 记忆化：

   • 对当前剩余分数数组排序
   • 哈希后查表

4. 输出答案

复杂度分析

• 状态数：$O(\text{不同的分数组合})$
• 每个状态的转移：$O(3)$
• 总时间复杂度：难以精确估计，但通过记忆化和剪枝能有效控制
• 空间复杂度：$O(\text{状态数} \times n)$

#include<bits/stdc++.h>
#define maxn 12
#define mo 1000000007
#define lc 28
#define LL long long
using namespace std;
LL n,ans;
LL a[maxn],tmp[maxn],sum[maxn];
LL sx,sy,s;
map<LL,LL> M;
LL cmp(LL x,LL y){
    return x>y;
}
LL dfs(LL x,LL y){
    LL now=0;
    if(x>=n){
    	return 1;
	}
    if(y>n){
        if(tmp[x]!=a[x]){
        	return 0;
		}
        for(LL i=x+1;i<=n;i++){
        	sum[i]=a[i]-tmp[i];
		}
        sort(sum+x+1,sum+n+1);
        LL hah=0;
        for(LL i=x+1;i<=n;i++){
        	hah=hah*lc+sum[i];
		}
        if(M.find(hah)!=M.end()){
        	return M[hah];
		}
        return M[hah]=dfs(x+1,x+2);
    }
    if(tmp[x]+3<=a[x] && sx){
    	tmp[x]+=3;
		sx--;
		now+=dfs(x,y+1);
		tmp[x]-=3;
		sx++;
	}
    if(tmp[y]+3<=a[y] && sx){
    	tmp[y]+=3;
		sx--;
		now+=dfs(x,y+1);
		tmp[y]-=3;
		sx++;
	}
    if(tmp[x]+1<=a[x] && tmp[y]+1<=a[y] && sy){
    	tmp[x]+=1;
		tmp[y]+=1;
		sy--;
		now+=dfs(x,y+1);
		tmp[x]-=1;
		tmp[y]-=1;
		sy++;
	}
    return now%mo;
}
int main(){
    scanf("%lld",&n);
    for(LL i=1;i<=n;i++){
    	scanf("%lld",&a[i]);
		s+=a[i];
	}
    sx=s-n*n+n;sy=(n*n-n)/2-sx;
    sort(a+1,a+n+1,cmp);
    printf("%lld",dfs(1,2));
    return 0;
}

题解

题目给出了最终积分榜，其中胜利得 3 分、平局双方各得 1 分、失败得 0 分。设 $n$ 支队伍的总积分之和为 $s$，则可以推算出胜场数 $W = s - n(n-1)$（相比全部平局多出的积分正好是胜场数），而平局场数 $D = \binom{n}{2} - W$。因此我们只需统计所有满足这两个数字的比赛结果方案数。

按照队伍编号从小到大逐对填充比赛结果：枚举队伍 $x$ 与更高编号的队伍 $y$ 的对局，可以让 $x$ 胜、$y$ 胜或双方打平。我们用 sx、sy 记录剩余可用的胜场和和局场数，因此每次设定结果前都要判断是否还有额度。tmp[i] 表示当前为队伍 $i$ 已经累积的积分，当 $y > n$ 时说明队伍 $x$ 已经和所有对手比完了，此时必须严格等于目标积分 a[x]，否则该分支无效。

由于不同队伍积分相同会导致大量对称情况，需要在每次完成队伍 $x$ 的所有比赛后，把剩余队伍的“还差多少分”排序，利用哈希表记忆化搜索以避免重复。这样整棵搜索树的状态数量可控，最终答案即为所有合法搜索路径的计数并对模数取值。代码中使用递归回溯配合记忆化，复杂度对 $n \le 12$ 完全可行。

#include<bits/stdc++.h>
#define maxn 12
#define mo 1000000007
#define lc 28
#define LL long long
using namespace std;
LL n,ans;
LL a[maxn],tmp[maxn],sum[maxn];
LL sx,sy,s;
map<LL,LL> M;
LL cmp(LL x,LL y){
    return x>y;
}
LL dfs(LL x,LL y){
    LL now=0;
    if(x>=n){
    	return 1;
	}
    if(y>n){
        if(tmp[x]!=a[x]){
        	return 0;
		}
        for(LL i=x+1;i<=n;i++){
        	sum[i]=a[i]-tmp[i];
		}
        sort(sum+x+1,sum+n+1);
        LL hah=0;
        for(LL i=x+1;i<=n;i++){
        	hah=hah*lc+sum[i];
		}
        if(M.find(hah)!=M.end()){
        	return M[hah];
		}
        return M[hah]=dfs(x+1,x+2);
    }
    if(tmp[x]+3<=a[x] && sx){
    	tmp[x]+=3;
		sx--;
		now+=dfs(x,y+1);
		tmp[x]-=3;
		sx++;
	}
    if(tmp[y]+3<=a[y] && sx){
    	tmp[y]+=3;
		sx--;
		now+=dfs(x,y+1);
		tmp[y]-=3;
		sx++;
	}
    if(tmp[x]+1<=a[x] && tmp[y]+1<=a[y] && sy){
    	tmp[x]+=1;
		tmp[y]+=1;
		sy--;
		now+=dfs(x,y+1);
		tmp[x]-=1;
		tmp[y]-=1;
		sy++;
	}
    return now%mo;
}
int main(){
    scanf("%lld",&n);
    for(LL i=1;i<=n;i++){
    	scanf("%lld",&a[i]);
		s+=a[i];
	}
    sx=s-n*n+n;sy=(n*n-n)/2-sx;
    sort(a+1,a+n+1,cmp);
    printf("%lld",dfs(1,2));
    return 0;
}