话说这题真的有紫吗（问号
注意到数据范围中提到 $\sum{nm} \le 2 \times 10^5 $，这里实际上是隐含了 \(\min(n,m) \le \sqrt{2\times 10^5}\) 的。我们考虑根据 \(n\) 和 \(m\) 的大小关系设计出不同的算法。
- \(m<n\)
一个比较直接的想法是对于每一个科目先按该科目的分数排序，这样我们只需要考虑相邻两个人的关系即可。
对于排名相邻的两种分数的人，最坏情况下的赋值一定是把剩下的权值全部给后面一名的优势科目，若枚举到第 \(j\) 个科目，第 \(i\) 个人，后面的人超出前面的人最多分数的科目为 \(k\) 的话，那么 \(p_k\) 需满足：
\[p_j \times (a_{i,j} - a_{i-1,j}) > (1-p_j) \times (a_{i-1,k} - a_{i,k}) \]直接计算，最后取最大值即可。时间复杂度 \(O(nm^2)\)。
- \(n<m\)
和上一种情况类似，但这一次我们要尽量避免枚举 \(m\)。
双层循环枚举学生 \(i\) 和 \(j\)，遍历每一科目，先找到 \(j\) 相对 \(i\) 的优势科目，再对任意 \(k\) 使得 \(c_{i,k} > c_{j,k}\) （即 \(i\) 的排名比 \(j\) 高）计算贡献即可。
时间复杂度 \(O(n^2m)\)。
代码
#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
char ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
const int N=1e5+5,mod=998244353;
int T,n,m;
struct node{vector<int> v;}a[N],tmp[N],tmp2[N];
inline int KSM(int x,int n){
int ans=1;
while(n){
if(n&1)ans=1ll*x*ans%mod;
x=1ll*x*x%mod;
n>>=1;
}
return ans;
}
namespace m2n{
inline void Solve(){
for(int j=0;j<m;j++){
int mxm=1,mxz=0,cnt=0;
sort(a+1,a+n+1,[=](node a,node b){return a.v[j]<b.v[j];});
tmp[++cnt]=a[1];tmp2[cnt]=a[1];
for(int i=2;i<=n;i++){
if(a[i].v[j]!=a[i-1].v[j])tmp[++cnt]=a[i],tmp2[cnt]=a[i];
else {
for(int k=0;k<m;k++)
tmp[cnt].v[k]=min(tmp[cnt].v[k],a[i].v[k]),
tmp2[cnt].v[k]=max(tmp2[cnt].v[k],a[i].v[k]);
}
}
for(int i=2;i<=cnt;i++){
int c1=tmp[i].v[j]-tmp[i-1].v[j],c2=0;
for(int k=0;k<m;k++){
if(k==j)continue;
c2=max(c2,tmp2[i-1].v[k]-tmp[i].v[k]);
}
if(!c2)continue;
if(1ll*c2*mxm>1ll*(c1+c2)*mxz)mxm=c1+c2,mxz=c2;
}
printf("%lld\n",1ll*mxz*KSM(mxm,mod-2)%mod);
}
for(int i=1;i<=n;i++)a[i].v.clear();
}
}
namespace n2m{
int mxz[N],mxm[N];
inline void Solve(){
for(int i=0;i<=m;i++)mxz[i]=0,mxm[i]=1;
for(int x=1;x<=n;x++){
for(int y=1;y<=n;y++){
if(x==y)continue;
int c2=0;
for(int i=0;i<m;i++)
c2=max(c2,a[y].v[i]-a[x].v[i]);
for(int i=0;i<m;i++){
if(a[y].v[i]>=a[x].v[i])continue;
int c1=a[x].v[i]-a[y].v[i];
if(a[x].v[i]>a[y].v[i])
if(1ll*(c1+c2)*mxz[i]<1ll*mxm[i]*c2)mxm[i]=c1+c2,mxz[i]=c2;
}
}
}
for(int i=0;i<m;i++)
printf("%lld\n",1ll*mxz[i]*KSM(mxm[i],mod-2)%mod);
for(int i=1;i<=n;i++)a[i].v.clear();
}
}
signed main(){
rd(T);
while(T--){
rd(n,m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;rd(x);
a[i].v.push_back(x);
}
}
if(n<=m)n2m::Solve();
else m2n::Solve();
}
return 0;
}