HNOI2013 比赛

P3230 [HNOI2013] 比赛

题目大意

有$n$支球队比赛，每两支球队之间踢一场比赛，如果平局，则两支球队各得$1$分；否则，胜利的球队得$3$分，败者不得分。现在给出所有比赛结束后每支球队的得分，求有多少种可能的比赛过程。输出答案模$10^9+7$后的值。

$3\le n\le 10$，数据保证至少存在一组解。

题解

我们发现$n$比较小，可以考虑搜索。按编号从小到大来处理球队，假设当前处理到第$i$支球队，则继续搜索并处理$i$和$i+1～n$的比赛结果，然后继续处理第$i+1$支球队。

不过，直接搜索肯定是不行的，我们要加一些剪枝。

剪枝1

如果一个球队当前的分数大于其总分，则结束搜索。

剪枝2

如果当前枚举的这支球队在之后的比赛中全赢也达不到其应得的分数，则结束搜索。

剪枝3

令所有队伍的总得分为$sum$，设能分出胜负的比赛场数为$wn$，平局的场数为$dr$，于是我们可以列出方程组

$$?\begin{array}{c}wn+dr=\frac{n(n?1)}{2}\\ \\ 3wn+2dr=sum\end{array}$$

得到$wn=sum?n(n?1)$，$dr=\frac{n(n?1)}{2}?wn$。在搜索的时候，要保证分出胜负的比赛的次数不超过$wn$，平局的场数不超过$dr$。

剪枝4

我们发现，在处理完前$i$个人之后，前$i$个人的分数在之后的比赛中是不会改变的，那么前$i$个人当前的分数都应该和其应得的分数相同。对于第$i+1～n$支球队，我们可以用哈希来表示这些人的分数，然后用记忆化搜索来将对应哈希值的答案存下来。因为不同的球队是等价的，我们可以在求哈希值的时候将第$i+1～n$支球队的分数从小到大排序，这样可以减少状态数。

注意为了避免前导零的影响，求哈希值的时候每一位都要$+1$。

code

#include<bits/stdc++.h>
using namespace std;
const int base=29;
const long long mod=1e9+7;
int n,sum=0,ans=0,a[15],b[15];
map<long long,long long>mp;
long long dfs(int i,int j,int wn,int dr){
	if(i==n) return 1;
	if(a[i]-3*(n-j+1)>0) return 0;
	if(j>n){
		for(int o=1;o<=i;o++){
			if(a[i]) return 0;
		}
		for(int o=i+1;o<=n;o++) b[o]=a[o];
		sort(b+i+1,b+n+1);
		long long hsh=0;
		for(int o=i+1;o<=n;o++){
			hsh=hsh*base+b[o]+1;
		}
		if(mp.count(hsh)) return mp[hsh];
		return mp[hsh]=dfs(i+1,i+2,wn,dr);
	}
	long long re=0;
	if(a[i]>=3&&wn){
		a[i]-=3;
		re+=dfs(i,j+1,wn-1,dr);
		a[i]+=3;
	}
	if(a[j]>=3&&wn){
		a[j]-=3;
		re+=dfs(i,j+1,wn-1,dr);
		a[j]+=3;
	}
	if(a[i]>=1&&a[j]>=1&&dr){
		--a[i];--a[j];
		re+=dfs(i,j+1,wn,dr-1);
		++a[i];++a[j];
	}
	return re%mod;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	int wn,dr;
	wn=sum-n*(n-1);
	dr=n*(n-1)/2-wn;
	printf("%lld",dfs(1,2,wn,dr));
	return 0;
}