https://ac.nowcoder.com/acm/contest/393/C

题意

给你一个矩阵, 每次从每行挑选一个数,组成一个排列,排列的和为不重复数字之和,求所有排列的和(n,m<=2000,a[i]<=1e9)

题解

• 假如计算数字x的贡献的话,x只会对所在排列最多贡献一次,那么只需要计算有多少排列含有x
• 反着计算每个数字的贡献,(总情况-包含这个数字的情况)*x

代码

#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;

}