ABC E题求调
  • 板块学术版
  • 楼主C202301
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/6/21 21:56
  • 上次更新2025/6/22 17:04:10
查看原帖
ABC E题求调
975726
C202301楼主2025/6/21 21:56

样例都没过,想问一下思路是不是正确的,大体就是枚举可能成为最大值的每一个数,并算概率求和。

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll Q,mod=998244353,E[600005],xx,d[100005],R,all=0;
bool flag=0,lst;
struct node{
	ll a,x;
}nd[600005];
bool cmp(node a,node b){
	if(a.a==b.a) return a.x<b.x;
	return a.a<b.a;
}
ll qpow(ll x,ll y) {
	ll ans=1;
	while(y) {
		if(y&1) ans*=x,ans%=mod;
		x*=x,x%=mod;
		y>>=1;
	}
	return ans;
}
int main()
{
	int n,tot=0;
	cin>>n;
	Q=qpow(6,n);
	Q=qpow(Q,mod-2);
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=6;j++) cin>>xx,nd[++tot].a=xx,nd[tot].x=i;
	sort(nd+1,nd+tot+1,cmp);
	d[nd[1].x]++;
	for(int i=2;i<=tot;i++) 
		if(nd[i].a<=nd[1].a) d[nd[i].x]++;
	E[1]=nd[1].a;
	for(int i=1;i<=n;i++) {
		if(i!=nd[1].x) E[1]*=d[i],E[1]%=mod;
		if(d[i]>0) all++;
	}
	if(all==n) flag=1;
	R=E[1];
	lst=flag;
	for(int i=2;i<=tot;i++) {
		if(nd[i].x==nd[i-1].x) {
			E[i]=E[i-1]*nd[i].a%mod*qpow(nd[i-1].a,mod-2)%mod;
		}
		else {
			E[i]=E[i-1];
			if(flag) {
				if(!lst) {
					E[i]=1;
					for(int j=1;j<=n;j++) E[i]*=d[i],E[i]%=mod;
					E[i]=E[i]*nd[i].a%mod;
				}
				else E[i]=E[i]*d[nd[i-1].x]%mod*qpow(d[nd[i].x],mod-2)
				%mod*nd[i].a%mod*qpow(nd[i-1].a,mod-2)%mod;
			}  
		}
		R=(R+E[i])%mod;
		d[nd[i].x]++;
		lst=flag;
		if(d[nd[i].x]==1) all++;
		if(all==n) flag=1;
	}
	cout<<Q*R%mod;
	return 0;
}
2025/6/21 21:56
加载中...