为了使得大家高兴,小Q特意出个自认为的简单题(easy)来满足大家,这道简单题是描述如下:
有一个数列A已知对于所有的A[i]都是1~n的自然数,并且知道对于一些A[i]不能取哪些值,我们定义一个数列的积为该数列所有元素的乘积,要求你求出所有可能的数列的积的和 mod 1000000007的值,是不是很简单呢?呵呵!

第一行三个整数n,m,k分别表示数列元素的取值范围,数列元素个数,以及已知的限制条数。
接下来k行,每行两个正整数x,y表示A[x]的值不能是y。

一行一个整数表示所有可能的数列的积的和对1000000007取模后的结果。如果一个合法的数列都没有,答案输出0。

  1. 3 4 5
  2. 1 1
  3. 1 1
  4. 2 2
  5. 2 3
  6. 4 3
  1. 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

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

首先我们想一下如果没有限制那么最后的结果是多少.对于数列中的每一项,我们都可以取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个得到的结果乘起来,就是最后结果了.

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <map>
  6. #include <iostream>
  7. using namespace std;
  8. typedef long long ll;
  9. const int maxn=1e5+5;
  10. const ll Mod=1000000007;
  11. map<pair<ll,ll>,ll> ma1;
  12. map<ll,ll> ma2;
  13. ll hj[maxn],n,m,k,js;
  14. ll cf(ll now,ll zs){
  15. ll jl=now%Mod,ans=1;
  16. while(zs){
  17. if(zs&1)ans=(ans*(jl%Mod))%Mod;
  18. jl=(jl*(jl%Mod))%Mod;
  19. zs>>=1;
  20. }
  21. return ans;
  22. }
  23. int main(){
  24. scanf("%lld%lld%lld",&n,&m,&k);
  25. for(ll i=1;i<=k;++i){
  26. ll x,y;
  27. scanf("%lld%lld",&x,&y);
  28. if(!ma2[x]) hj[++js]=x;
  29. if(ma1[make_pair(x,y)])continue;
  30. ma1[make_pair(x,y)]=1;
  31. ma2[x]+=y;
  32. }
  33. ll ans=1,cj=(n+1)*n/2;
  34. for(ll i=1;i<=js;++i)
  35. ans=(ans*((cj-ma2[hj[i]])%Mod))%Mod;
  36. printf("%lld\n",(ans%Mod)*(cf(cj,m-js)%Mod)%Mod);
  37. return 0;
  38. }

hzoi

版权声明:本文为Lour688原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/Lour688/p/12886503.html