自动搬运

查看原文

来自洛谷，原作者为

	hzoi_liuchang AFO

搬运于2025-08-24 21:35:17，当前版本为作者最后更新于2020-05-12 19:13:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

我们先去考虑没有限制的情况，那么最终的答案就是

$( 1+2+3+……+n)^{m}=(\frac{n\times(n-1)}{2})^{m}$

为什么是这样呢？其实我们可以把数列的每一个元素看成一个集合

每一次我们可以从每个集合中任意取出$n$个元素

这$n$个元素的值分别为$1 - n$

根据乘法原理最终的结果就是

$(1+2+3+……+n)\times(1+2+3+……+n)\times……$

一共要乘$m$次

如果还不理解的话，你可以随便举一个例子，按照上面的式子把它展开

但是，题目中有些元素是取不到的

我们可以记录一下每一个元素取不到的值的和$tot$

我们只要把该元素贡献的价值改为$\frac{n\times(n-1)}{2}-tot$就可以了

因为题目中的限制条件最多只有$10^{5}$个

所以我们记录下有限制条件的元素的个数$cnt$，对其单独处理

对于其余的元素，我们用快速幂的思想求出$(\frac{n\times(n-1)}{2})^{m-cnt}$

最后再把所有的结果累乘就可以了

要注意两个问题： 1、因为结果很大，能取模的地方就取模 2、要注意判重，样例已经给出重复的情况了

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const long long mod=1e9+7;
typedef long long ll;
map<pair<ll,ll>,ll> ma1;
map<ll,ll> ma2;
ll jl[maxn];
ll cf(ll now,ll zs){
    ll jl=now%mod,ans=1;
    while(zs){
        if(zs&1) ans*=(jl%mod),ans%=mod;
        jl*=(jl%mod),jl%=mod;
        zs>>=1;
    }
    return ans;
}
int main(){
    ll n,m,k,js=0;
    scanf("%lld%lld%lld",&n,&m,&k);
    for(ll i=1;i<=k;i++){
        ll aa,bb;
        scanf("%lld%lld",&aa,&bb);
        if(!ma2[aa]) jl[++js]=aa;
        if(ma1[make_pair(aa,bb)]) continue;
        ma1[make_pair(aa,bb)]=1;
        ma2[aa]+=bb;
    }
    ll ans=1,cj=(n+1)*n/2;
    for(ll i=1;i<=js;i++){
        ans*=(cj-ma2[jl[i]])%mod;
	    ans%=mod;
    }
    printf("%lld\n",ans%mod*cf(cj,m-js)%mod%mod);
    return 0;
}