Describe
为了使得大家高兴，小Q特意出个自认为的简单题（easy）来满足大家，这道简单题是描述如下：
有一个数列A已知对于所有的A[i]都是1~n的自然数，并且知道对于一些A[i]不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积，要求你求出所有可能的数列的积的和 mod 1000000007的值，是不是很简单呢？呵呵！
Input
第一行三个整数n,m,k分别表示数列元素的取值范围，数列元素个数，以及已知的限制条数。
接下来k行，每行两个正整数x,y表示A[x]的值不能是y。
Output
一行一个整数表示所有可能的数列的积的和对1000000007取模后的结果。如果一个合法的数列都没有，答案输出0。
Sample Input
3 4 5
1 1
1 1
2 2
2 3
4 3
Sample Output
90
Explain
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
30%的数据n<=4,m<=10,k<=10
另有20%的数据k=0
70%的数据n<=1000,m<=1000,k<=1000
100%的数据 n<=10^9, m<=10^9, k<=10^5,1<=y<=n,1<=x<=m
Solution
首先我们想一下如果没有限制那么最后的结果是多少.对于数列中的每一项,我们都可以取1~n,共有m项,最后总结果其实挺整齐的,$(1+2+3+......+n) * (1+2+3+......n) *...... *(1+2+3+......n) $共乘m次,因为每个数都可以从每乘一次的数(1 ~ n)中选一个算出数列的积,最后相加,化简 ((1+2+3+4+......+n)^m) ,也就是(((1+n)*n/2)^m) .可以看做用了分步乘法原理,共有m次方,也就是每个数对结果的贡献.
如果一个数被限制了,那么这个数所在的某一次方中就不是1 ~ n的加和了,要减去被限制的数,没有被限制的数还是1 ~ n加和,最后m个数遍历完,将m个得到的结果乘起来,就是最后结果了.
Attention
数据范围如此之大,快速幂!!!
注意取模,只要对结果没影响就取模.
去重边,样例中就有
Code
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const ll Mod=1000000007;
map<pair<ll,ll>,ll> ma1;
map<ll,ll> ma2;
ll hj[maxn],n,m,k,js;
ll cf(ll now,ll zs){
ll jl=now%Mod,ans=1;
while(zs){
if(zs&1)ans=(ans*(jl%Mod))%Mod;
jl=(jl*(jl%Mod))%Mod;
zs>>=1;
}
return ans;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(ll i=1;i<=k;++i){
ll x,y;
scanf("%lld%lld",&x,&y);
if(!ma2[x]) hj[++js]=x;
if(ma1[make_pair(x,y)])continue;
ma1[make_pair(x,y)]=1;
ma2[x]+=y;
}
ll ans=1,cj=(n+1)*n/2;
for(ll i=1;i<=js;++i)
ans=(ans*((cj-ma2[hj[i]])%Mod))%Mod;
printf("%lld
",(ans%Mod)*(cf(cj,m-js)%Mod)%Mod);
return 0;
}
hzoi