设$t=\frac{n(n+1)}{2}$
$k=0$时，显然$ans=m^t$
仅考虑一个位置$x$不可用的数$y$，$x$位置对总积的贡献即为$t-y$
此时$ans=(m-1)^t*(t-y)$
于是我们把所有位置去重一下
快速幂统计完好的位置，部分残缺的位置直接枚举统计
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; int read(){ char c=getchar(); int x=0; while(c<‘0‘||c>‘9‘) c=getchar(); while(‘0‘<=c&&c<=‘9‘) x=x*10+c-48,c=getchar(); return x; } const ll P=1e9+7; int k,tk,m; ll n,t,ans; struct Lim{int x;ll y;}a[100005]; int cmp(Lim A,Lim B){return A.x==B.x?A.y<B.y:A.x<B.x;} ll Pow(ll x,ll y){ll re=1; for(;y;y>>=1,x=x*x%P)if(y&1)re=re*x%P; return re;} int main(){ n=read(); m=read(); k=read(); t=n*(n+1)/2; for(int i=1;i<=k;++i) a[i].x=read(),a[i].y=read(); sort(a+1,a+k+1,cmp); for(ll i=1,s=0;i<=k;++i){ if(a[i].x==a[i+1].x){ if(a[i].y!=a[i+1].y) s+=a[i].y; }else a[i].y+=s,a[++tk]=a[i],s=0; }ans=Pow(t%P,m-tk); for(int i=1;i<=tk;++i) ans=(t-a[i].y)%P*ans%P; printf("%lld",ans); return 0; }
原文：https://www.cnblogs.com/kafuuchino/p/11488337.html