点击查看代码
#include<bits/stdc++.h>
#define _ num[i]
using namespace std;
const int maxn=1e5+9;
const int mod=998244353;
int n,cnt,ans,s[7][maxn],num[maxn<<3];
int low(int x,int id){return lower_bound(s[id]+1,s[id]+n+1,x)-s[id]-1;}
int up(int x,int id){return n-(upper_bound(s[id]+1,s[id]+n+1,x)-s[id]-1);}
int same(int x,int id){return upper_bound(s[id]+1,s[id]+n+1,x)-lower_bound(s[id]+1,s[id]+n+1,x);}
int main(){
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=5;i++){
for(int j=1;j<=n;j++){
scanf("%d",&s[i][j]);
num[++cnt]=s[i][j];
}
sort(s[i]+1,s[i]+n+1);
}
sort(num+1,num+cnt+1);
cnt=unique(num+1,num+cnt+1)-num-1;
for(int i=1;i<=cnt;i++){
int tmp=0;long long sm=0;
sm=same(_,1);
if(sm){
(tmp+=sm*low(_,2)%mod*low(_,3)%mod*up(_,4)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,4)%mod*up(_,3)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,5)%mod*up(_,3)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,4)%mod*up(_,2)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,5)%mod*up(_,2)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,5)%mod*up(_,2)%mod*up(_,3)%mod)%=mod;
}
sm=same(_,2);
if(sm){
(tmp+=sm*low(_,1)%mod*low(_,3)%mod*up(_,4)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,4)%mod*up(_,3)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,5)%mod*up(_,3)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,4)%mod*up(_,1)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,5)%mod*up(_,1)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,5)%mod*up(_,1)%mod*up(_,3)%mod)%=mod;
}
sm=same(_,3);
if(sm){
(tmp+=sm*low(_,2)%mod*low(_,1)%mod*up(_,4)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,4)%mod*up(_,1)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,5)%mod*up(_,1)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,4)%mod*up(_,2)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,5)%mod*up(_,2)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,5)%mod*up(_,2)%mod*up(_,1)%mod)%=mod;
}
sm=same(_,4);
if(sm){
(tmp+=sm*low(_,2)%mod*low(_,3)%mod*up(_,1)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,1)%mod*up(_,3)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,5)%mod*up(_,3)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,1)%mod*up(_,2)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,5)%mod*up(_,2)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,5)%mod*up(_,2)%mod*up(_,3)%mod)%=mod;
}
sm=same(_,5);
if(sm){
(tmp+=sm*low(_,2)%mod*low(_,3)%mod*up(_,4)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,4)%mod*up(_,3)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,1)%mod*up(_,3)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,4)%mod*up(_,2)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,1)%mod*up(_,2)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,1)%mod*up(_,2)%mod*up(_,3)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,2)%mod;
if(sm){
(tmp+=sm*low(_,3)%mod*low(_,4)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,5)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,5)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,4)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,5)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*up(_,5)%mod*up(_,3)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,3)%mod;
if(sm){
(tmp+=sm*low(_,2)%mod*low(_,4)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,5)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,5)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*up(_,4)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*up(_,5)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*up(_,5)%mod*up(_,2)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,4)%mod;
if(sm){
(tmp+=sm*low(_,3)%mod*low(_,2)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,5)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,5)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,2)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,5)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*up(_,5)%mod*up(_,3)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,3)%mod*low(_,4)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,2)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,2)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,4)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,2)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*up(_,2)%mod*up(_,3)%mod)%=mod;
}
sm=1ll*same(_,2)*same(_,3)%mod;
if(sm){
(tmp+=sm*low(_,1)%mod*low(_,4)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,5)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,5)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*up(_,4)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*up(_,5)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*up(_,5)%mod*up(_,1)%mod)%=mod;
}
sm=1ll*same(_,2)*same(_,4)%mod;
if(sm){
(tmp+=sm*low(_,3)%mod*low(_,1)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,5)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,5)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,1)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,5)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*up(_,5)%mod*up(_,3)%mod)%=mod;
}
sm=1ll*same(_,2)*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,3)%mod*low(_,4)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,1)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,1)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,4)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,1)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*up(_,1)%mod*up(_,3)%mod)%=mod;
}
sm=1ll*same(_,3)*same(_,4)%mod;
if(sm){
(tmp+=sm*low(_,1)%mod*low(_,2)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,5)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,5)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*up(_,2)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*up(_,5)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*up(_,5)%mod*up(_,1)%mod)%=mod;
}
sm=1ll*same(_,3)*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,1)%mod*low(_,2)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,4)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,4)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*up(_,2)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*up(_,4)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*up(_,4)%mod*up(_,1)%mod)%=mod;
}
sm=1ll*same(_,4)*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,1)%mod*low(_,2)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,3)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*low(_,3)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*up(_,2)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*up(_,3)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*up(_,3)%mod*up(_,1)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,2)%mod*same(_,3)%mod;
if(sm){
(tmp+=sm*low(_,4)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,5)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,5)%mod)%=mod;
(tmp+=sm*up(_,5)%mod*up(_,4)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,2)%mod*same(_,4)%mod;
if(sm){
(tmp+=sm*low(_,3)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,5)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,5)%mod)%=mod;
(tmp+=sm*up(_,5)%mod*up(_,3)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,2)%mod*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,4)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,4)%mod)%=mod;
(tmp+=sm*up(_,4)%mod*up(_,3)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,3)%mod*same(_,4)%mod;
if(sm){
(tmp+=sm*low(_,2)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,5)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,5)%mod*low(_,2)%mod)%=mod;
(tmp+=sm*up(_,2)%mod*up(_,5)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,3)%mod*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,4)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*low(_,2)%mod)%=mod;
(tmp+=sm*up(_,2)%mod*up(_,4)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,4)%mod*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,2)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*low(_,2)%mod)%=mod;
(tmp+=sm*up(_,2)%mod*up(_,3)%mod)%=mod;
}
sm=1ll*same(_,2)*same(_,3)%mod*same(_,4)%mod;
if(sm){
(tmp+=sm*low(_,1)%mod*up(_,5)%mod)%=mod;
(tmp+=sm*low(_,5)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,5)%mod)%=mod;
(tmp+=sm*up(_,5)%mod*up(_,1)%mod)%=mod;
}
sm=1ll*same(_,2)*same(_,3)%mod*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,1)%mod*up(_,4)%mod)%=mod;
(tmp+=sm*low(_,4)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,4)%mod)%=mod;
(tmp+=sm*up(_,4)%mod*up(_,1)%mod)%=mod;
}
sm=1ll*same(_,2)*same(_,4)%mod*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,1)%mod*up(_,3)%mod)%=mod;
(tmp+=sm*low(_,3)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,3)%mod)%=mod;
(tmp+=sm*up(_,3)%mod*up(_,1)%mod)%=mod;
}
sm=1ll*same(_,3)*same(_,4)%mod*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,1)%mod*up(_,2)%mod)%=mod;
(tmp+=sm*low(_,2)%mod*up(_,1)%mod)%=mod;
(tmp+=sm*low(_,1)%mod*low(_,2)%mod)%=mod;
(tmp+=sm*up(_,2)%mod*up(_,1)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,2)%mod*same(_,3)%mod*same(_,4)%mod;
if(sm){
(tmp+=sm*low(_,5)%mod)%=mod;
(tmp+=sm*up(_,5)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,2)%mod*same(_,3)%mod*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,4)%mod)%=mod;
(tmp+=sm*up(_,4)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,2)%mod*same(_,4)%mod*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,3)%mod)%=mod;
(tmp+=sm*up(_,3)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,3)%mod*same(_,4)%mod*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,2)%mod)%=mod;
(tmp+=sm*up(_,2)%mod)%=mod;
}
sm=1ll*same(_,2)*same(_,3)%mod*same(_,4)%mod*same(_,5)%mod;
if(sm){
(tmp+=sm*low(_,1)%mod)%=mod;
(tmp+=sm*up(_,1)%mod)%=mod;
}
sm=1ll*same(_,1)*same(_,2)%mod*same(_,3)%mod*same(_,4)%mod*same(_,5)%mod;
if(sm) (tmp+=sm)%=mod;
(ans+=1ll*_*tmp%mod)%=mod;
}
return printf("%d\n",ans),0;
}