aaa掉了我1%的正确率
就是直接每一个位置可以取的值之和的乘积就是ans
但是鉴于k非常小但是m非常大，所以有很多的位置可以取1~n，这些位置直接快速幂就可以了
下面是代码(能AC算我输)
#include<iostream> #include<algorithm> using namespace std; const long long mod=1000000007; long long n,m,k; long long ans=1; struct hehe{ long long pos,val; }a[100010]; bool cmp(const hehe a,const hehe b){ if(a.pos==b.pos){ return a.val<b.val; }else{ return a.pos<b.pos; } } long long qpow(long long a,long long b){ if(b==1){ return a; }else{ long long fanhui=qpow(a,b/2); fanhui=fanhui%mod; if(b%2==1){ fanhui=fanhui*a; fanhui=fanhui%mod; } return fanhui; } } int main(){ cin>>n>>m>>k; for(int i=1;i<=k;i++){ cin>>a[i].pos>>a[i].val; } sort(a+1,a+k+1,cmp); long long zong=m; long long x=1,y=1; for(;;){ long long sum=n*(n+1)/2; while(a[x].pos==a[y].pos&&y<=k){ y++; } y--; zong--; sum-=a[x].val; for(int i=x+1;i<=y;i++){ if(a[i].val!=a[i-1].val){ sum-=a[i].val; } } ans*=sum; ans%=mod; y++; x=y; if(y==k+1){ break; } } ans=ans*qpow((n*(n+1)/2),zong); ans%=mod; cout<<ans<<endl; return 0; } /* in: 3 4 5 1 1 1 1 2 2 2 3 4 3 out: 90 */