C++14(g++5.4) 解法, 执行用时: 1641ms, 内存消耗: 33468K, 提交时间: 2019-03-17 15:33:24

#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> PII;
const int MOD = 1000000007;
vector<PII> arr;
int ans, cnt;
int quick_pow(int n, int k) {
	int res = 1;
	while (k) {
		if (k & 1) {
			res = (res * 1LL * n) % MOD;
		}
		n = (n * 1LL * n) % MOD;
		k >>= 1;
	}
	return res;
}
int main() {
	int n, m, v;
	int i, j, k;
	scanf("%d%d", &m, &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &v);
			arr.push_back(make_pair(v, i));
		}
	}
	sort(arr.begin(), arr.end());
	int tot = arr.size();
	int p = quick_pow(m, n), inv = quick_pow(m, MOD - 2);
	for (i = 0; i < tot; i = j) {
		cnt = p;
		for (j = i; j < tot && arr[j].first == arr[i].first; j = k) {
			for(k = j; k < tot && arr[k].first == arr[i].first && arr[k].second == arr[j].second; k++);
			cnt = cnt * 1LL * (m - k + j) % MOD * inv % MOD;
		}
		ans = (ans + (p - cnt + MOD) * 1LL * arr[i].first) % MOD;
	}
	printf("%d\n", ans);
	return 0;
} 

C++11(clang++ 3.9) 解法, 执行用时: 1415ms, 内存消耗: 66312K, 提交时间: 2019-03-21 16:55:12

#include<bits/stdc++.h>
#define ft first
#define se second
#define MOD 1000000007
#define MAXN 2005
#define mk make_pair
#define ll long long 
#define pii pair<ll,ll>
using namespace std;
ll pw(ll bs,ll x){
	ll ans=1;
	while(x){
		if(x&1)ans=ans*bs%MOD;
		bs=bs*bs%MOD;
		x>>=1;
	}
	return ans;
}
ll n,m,i,j,x,inv[MAXN],tol,C[MAXN],ans,nt,tp;
vector<pii>A;
int main(){
	scanf("%lld%lld",&m,&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
			scanf("%lld",&x);
			A.push_back(mk(x,i));
		}
	inv[1]=1;for(i=2;i<MAXN;i++)inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
	sort(A.begin(),A.end());
	ll tol=pw(m,n);
	for(i=0;i<A.size();i=nt){
		tp=tol;
		for(nt=i;nt<A.size()&&A[i].ft==A[nt].ft;nt++){
			x=A[nt].se;
			tp=tp*inv[m-C[x]]%MOD;
			C[x]++;
			tp=tp*(m-C[x])%MOD;
		}
		for(j=i;j<nt;j++)C[A[j].se]=0;
		ans=(ans+(tol-tp+MOD)%MOD*A[i].ft%MOD)%MOD;
	}
	cout<<ans;
}