题目大意
洛谷链接
有一个数列A已知对于所有的(A[i])都是(1~n)的自然数，并且知道对于一些(A[i])不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积，要求你求出所有可能的数列的积的和 (mod 1000000007)的值。
输入格式
第一行三个整数(n,m,k)分别表示数列元素的取值范围，数列元素个数，以及已知的限制条数。
接下来(k)行，每行两个正整数(x,y)表示(A[x])的值不能是(y)。
输出格式
一行一个整数表示所有可能的数列的积的和对(1000000007)取模后的结果。如果一个合法的数列都没有，答案输出(0)。
样例输入
3 4 5
1 1
1 1
2 2
2 3
4 3
样例输出
90
样例解释
(A[1])不能取(1)
(A[2])不能取(2、3)
(A[4])能取(3)
所以可能的数列有以下(12)种
第一行为数列
第二行为积
2 1 1 1
2
2 1 1 2
4
2 1 2 1
4
2 1 2 2
8
2 1 3 1
6
2 1 3 2
12
3 1 1 1
3
3 1 1 2
6
3 1 2 1
6
3 1 2 2
12
3 1 3 1
9
3 1 3 2
18
思路
从一般到特殊，如果没有不能选的限制，因为每个元素可以把范围内每个数取到，可以得到结果是：
(( sum_{1le kle n}k)^m)
然而题目中提到有些元素的有些取值取不到，那么对应的元素的总价值把这些取值都减去再乘进去就可以了。剩下的没有动的元素直接累乘，注意要用到快速幂。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const long long mod=1e9+7;
map<pair<ll,ll>,ll> a;//学lc大佬用的pair...其实用结构体也可
map<ll,ll> b;
ll n,m,k,cnt;
ll vis[maxn];
ll qpow(ll now,ll x){//快速幂的板子
ll vis=now%mod,res=1;
while(x){
if(x&1){
res*=(vis%mod);
res%=mod;
}
vis*=(vis%mod);
vis%=mod;
x>>=1;
}
return res;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&k);
ll sum=(n+1)*n/2;
for(ll i=1;i<=k;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
if(!b[x])vis[++cnt]=x;
if(a[make_pair(x,y)])continue;//样例给出了重复限制，所以记一下
a[make_pair(x,y)]=1;
b[x]+=y;//记录限制的总和
}
ll ans=1;
for(ll i=1;i<=cnt;i++){
ans*=(sum-b[vis[i]])%mod;
ans%=mod;
}
printf("%lld
",((ans%mod)*qpow(sum,m-cnt)%mod)%mod);
return 0;
}