出题人题解 | #出题的诀窍#

原题解链接：https://ac.nowcoder.com/discuss/163610

给定一个二维数组 $\{A_{M,N}\}\backslash \{A\_\{M,N\}\backslash \}$，求：

${\sum }_{i_1=1}^N{\sum }_{i_2=1}^N\cdots {\sum }_{i_M=1}^N\mathbf{\text{SUM}}(A_{1,i_1},A_{2,i_2},\dots ,A_{M,i_M})(\mathrm{m}\mathrm{o}\mathrm{d}1000000007)\backslash sum\; \backslash limits\_\{i\_1=1\}^\{N\}\; \backslash sum\; \backslash limits\_\{i\_2=1\}^\{N\}\; \backslash dots\; \backslash sum\; \backslash limits\_\{i\_M=1\}^\{N\}\; \backslash textbf\{SUM\}\; (\; A\_\{1,i\_1\},A\_\{2,i\_2\},\; \backslash dots\; ,A\_\{M,i\_M\}\; )\; \backslash pmod\; \{1000000007\}$

其中 $\mathbf{\text{SUM}}(\text{一个序列})\backslash textbf\{SUM\}(\backslash text\{一个序列\})$表示这个序列中所有不同的数的和，相当于先 $\mathbf{s}\mathbf{o}\mathbf{r}\mathbf{t},\mathbf{u}\mathbf{n}\mathbf{i}\mathbf{q}\mathbf{u}\mathbf{e}\backslash bf\; sort,unique$ 再求和

其中$1\le n,m\le 2000,0\le A_{i,j}\le 10^{9}1\; \backslash le\; n,m\; \backslash le\; 2000,\; 0\; \backslash le\; A\_\{i,j\}\; \backslash le\; 10^9$

#include<bits/stdc++.h>
#define maxn 2010
#define ll long long
#define IL inline
using namespace std;

struct data{
	int x,idx,idy;
	bool operator <(const data &rhs)const{
		return x<rhs.x;
	}
}ds[maxn*maxn];
int val[maxn][maxn],rv[maxn*maxn],tn,n,m;
ll f[maxn*maxn],invn;
const ll p=1e9+7;
IL void read(int &x){
	char ch=x=0;
	while(!isdigit(ch))
		ch=getchar();
	while(isdigit(ch))
		x=x*10+ch-'0',ch=getchar();
}
ll pw(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&1)
			ret=ret*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ret;
}
int main(){
	read(n),read(m),invn=pw(n,p-2);
	for(int i=1,cnt=0;i<=m;i++){
		for(int j=1,x;j<=n;j++)
			read(ds[++cnt].x),ds[cnt].idx=i,ds[cnt].idy=j;
	}
	sort(ds+1,ds+m*n+1);
	for(int i=1;i<=m*n;i++)
		rv[val[ds[i].idx][ds[i].idy]=val[ds[i-1].idx][ds[i-1].idy]+(ds[i-1].x!=ds[i].x)]=ds[i].x;
	tn=val[ds[m*n].idx][ds[m*n].idy];
	for(int i=1;i<=tn;i++)
		f[i]=1;
	for(int i=1;i<=m;i++){
		sort(val[i]+1,val[i]+n+1);
		for(int j=1,pos=1;j<=n;j=pos+1){
			while(pos<n&&val[i][pos+1]==val[i][j])
				pos++;
			f[val[i][j]]=f[val[i][j]]*(n-pos+j-1)%p*invn%p;
		}
	}
	ll U=pw(n,m),ans=0;
	for(int i=1;i<=tn;i++)
		ans=(ans+1LL*rv[i]*(U-f[i]*U%p+p)%p)%p;
	printf("%lld\n",ans);
	return 0;
}