多校联测11 THUSC

题目大意

有$n$个人参加$THUSC$，第$i$个人算法场和工程场的成绩分别为$a_i$和$b_i$，保证不存在两个人两项成绩都相同。

现在招办想给他们排个名。一个合理的排名方案是分别给算法场和工程场一个正的权重$x,y$，然后按照$a_{i}x+b_{i}y$降序排名，相同的可以按照他们的心情排。

对于一个成绩分布，求有多少种可能的排名。

输出答案对$998244353$取模后的值。

$1\le n\le 1000,1\le a_i,b_i\le 10^9$

题解

因为当$x_1\ne x_2,y_1\ne y_2$且$\frac{x_1}{y_1}=\frac{x_2}{y_2}$时，权重为$x_1,y_1$和$x_2,y_2$所得的排名是相同的。所以，我们只需考虑比值$\frac{x}{y}$，令比值为$w=\frac{x}{y}$。

首先，我们把所有满足题意的$w$分成两个类型：

• 能使有至少两个人分数一样
• 能使任意两个人的分数不一样

因为存在分数一样的时候分数相同的任意排，所以所有第二种类型的$w$所得的排名都一定会在第一种类型的$w$所得的排名中出现。（可以自己举几个例子试一下）。

那么，我们只需要求能使至少两个人分数一样的$w$即可，而能使至少两个人分数一样的$w$不超过$n^2$个（对于任意两对$a_i,b_i$，只有一个$w$满足两者排名相同）。

枚举两个人$i,j$，求出能使$i,j$两个人分数相等的$w$。然后，我们只需考虑在每个不同的$w$作为比值的情况下有多少种排名即可。

这怎么处理呢？我们在求出能使$i,j$两个人分数相等的$w$的时候，在图上将$i,j$两点连一条权值为$w$的双向边，再从虚拟节点$n+1$向$i$连一条权值为$w$的单向边。等到全部边都连完了之后，对于每一个不同的$w$，看虚拟节点有多少个权值为$w$的边连出去。对于每个从虚拟节点指向的点$i$，看从$i$经过权值为$w$的边能够到达多少个点（包括自己），这些点当前的分数是与$i$的分数相同的。若能够到达$t$个点，则贡献为$t!$。换句话说，设$v_w$表示比值为$w$时不同排名的数量，则当得知$i$能到达$t$个点时，$v_w=v_w\times t!$。

在处理边的时候，我们可以将每个点连出的边按边权从小到大排序，那么走过的边就不用再走了，能保证每条边只会被遍历一次。

因为相邻的两个能使两人分数相等的$w$之间的那种排名会被计算两次，所以要减去，那么答案为$1+\sum (v_w-1)$。

枚举$i,j$的时间复杂度为$O(n^2)$，排序的时间复杂度为$O(n^2\log n)$。总共有不超过$3n^2$条边，每条边最多遍历一次，所以图上部分的时间复杂度为$O(n^2)$。所以，总时间复杂度为$O(n^2\log n)$。

code

#include
using namespace std;
const long long mod=998244353;
const int N=3000000;
int n,w1=0,now,z[N+5],to[1005];
long long ans=0,nd,a[1005],b[1005],jc[1005];
struct node{
	int a,b;
	long long x,y;
	bool operator==(const node ax)const{
		return x==ax.x&&y==ax.y;
	}
	bool operator!=(const node ax)const{
		return x!=ax.x||y!=ax.y;
	}
}w[1000005];
struct pr{
	int x,v;
};
vector<pr>g[1005];
bool cmp(node ax,node bx){
	if(ax.x!=bx.x) return ax.x<bx.x;
	return ax.y<bx.y;
}
long long gcd(long long i,long long j){
	while(j){
		i%=j;swap(i,j);
	}
	return i;
}
void dfs(int u,int t){
	if(z[u]==t) return;
	z[u]=t;
	++now;
	for(int i=to[u];i<g[u].size();++i,++to[u]){
		if(w[g[u][i].v]!=w[t]) break;
		dfs(g[u][i].x,t);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i],&b[i]);
	}
	jc[0]=1;
	for(int i=1;i<=1000;i++) jc[i]=jc[i-1]*i%mod;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			long long x=b[i]-b[j],y=a[j]-a[i],d;
			if(x*y<0) continue;
			if(x==0||y==0) continue;
			if(x<0){
				x=-x;y=-y;
			}
			d=gcd(x,y);
			x/=d;y/=d;
			w[++w1]=(node){i,j,x,y};
		}
	}
	sort(w+1,w+w1+1,cmp);
	for(int i=1;i<=w1;i++){
		g[w[i].a].push_back((pr){w[i].b,i});
		g[w[i].b].push_back((pr){w[i].a,i});
		g[n+1].push_back((pr){w[i].a,i});
	}
	for(int i=1;i<=w1;i++){
		if(i>1&&w[i]==w[i-1]) continue;
		nd=1;
		for(int j=to[n+1];j<g[n+1].size();++j,++to[n+1]){
			if(w[g[n+1][j].v]!=w[i]) break;
			now=0;
			dfs(g[n+1][j].x,i);
			nd=nd*jc[now]%mod;
		}
		ans=(ans+nd)%mod;
		ans=(ans-1+mod)%mod;
	}
	ans=(ans+1)%mod;
	printf("%lld",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82