多校联测11 THUSC-Toy模板网

这篇具有很好参考价值的文章主要介绍了多校联测11 THUSC。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目大意

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

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

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

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

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

题解

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

首先，我们把所有满足题意的 $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)$ 。文章来源地址https://www.toymoban.com/news/detail-727921.html

code

#include<bits/stdc++.h>
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;
}