P2220 [HAOI2012]容易题(快速幂)

Lour688 2020-05-14 原文

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

Sample Output

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\n",(ans%Mod)*(cf(cj,m-js)%Mod)%Mod);
	return 0;
}