样例都没过,想问一下思路是不是正确的,大体就是枚举可能成为最大值的每一个数,并算概率求和。
#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;
}