C++14(g++5.4) 解法, 执行用时: 2870ms, 内存消耗: 102520K, 提交时间: 2019-05-21 00:06:32

#include <bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
using namespace std;
typedef long long ll;
#define rint register int
const int maxn=6250007;
const int inf=(1LL<<29);
const int mod=1e9+7;
struct node{
    int x,p;
    bool operator < (node a) const{
        if(x!=a.x) return x<a.x;
        return p<a.p;
    }
}q[maxn];
int pown(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=(1LL*ans*a)%mod;
        a=(1LL*a*a)%mod;
        b>>=1;
    }
    return ans;
}
void add(int &x,int y){
    x+=y;if(x>mod) x-=mod;
}
int now[maxn],ans=1,cnt;
int main(){
    cin.tie(0);ios_base::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    for(int k=1;k<=n;k++){
        int x;cin>>x;
        q[(i-1)*n+k]={x,i};
    }
    sort(q+1,q+n*n+1);
    int tot=0;
    for(int i=1;i<=n*n;i++){
        node& a=q[i];
        if(now[a.p])ans=(1LL*ans*pown(now[a.p],mod-2))%mod;
        else cnt++;
        if(cnt==n) add(tot,(1LL*ans*a.x)%mod);
        now[a.p]++;
        ans=(1LL*ans*now[a.p])%mod;
    }
    cout<<1LL*tot*pown(pown(n,n),mod-2)%mod;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 2307ms, 内存消耗: 49272K, 提交时间: 2020-07-26 13:19:35

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int x,id;
}R[6250005];
bool cmp(node a,node b)
{
	return a.x>b.x;
}
const int mod=1e9+7;
long long fastpow(long long a,int b)
{
	long long s=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
	return s;
}
int main()
{
    int i,j,x,id=0,n,ans=0,T[2505];
    long long s=1;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)scanf("%d",&R[id].x),R[id++].id=i;
    sort(R,R+n*n,cmp);
    for(i=0;i<n;i++)T[i]=n,s=s*n%mod;
    for(i=0;i<n*n;i++)
    {
    	id=R[i].id,x=R[i].x;
		s=s*fastpow(T[id],mod-2)%mod;
		ans=(ans+s*x%mod)%mod;
		s=s*(--T[id])%mod;
	}
	printf("%d\n",ans*fastpow(fastpow(n,n),mod-2)%mod);
    return 0;
}