bzoj2751 容易题

传送门

题目

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

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

 

Output

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

分析

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<queue>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

long long cnt,num[];

const long long mod=1e9+;

struct node {

      long long x,y;

}a[];

inline long long pw(long long a,long long p){

      long long res=;

      a%=mod;

      while(p){

        if(p&)res=res%mod*(a%mod)%mod;

        a=a%mod*(a%mod)%mod;

        p>>=;

      }

      return res;

}

inline bool cmp(const node p,const node q){

      if(p.x==q.x)return p.y<q.y;

      return p.x<q.x;

}

int main(){

      long long n,m,i,j,k,t;

      scanf("%lld%lld%lld",&n,&m,&k);

      t=n*(n+)/%mod;

      for(i=;i<=k;i++){

        scanf("%lld%lld",&a[i].x,&a[i].y);

      }

      sort(a+,a+k+,cmp);

      for(i=;i<=k;i++){

        if(a[i].x!=a[i-].x)num[++cnt]=a[i].y;

          else if(a[i].y!=a[i-].y)num[cnt]=(num[cnt]+a[i].y)%mod;

      }

      long long ans=pw(t,m-cnt);

      for(i=;i<=cnt;i++)

        ans=ans%mod*(((t-num[i]+mod)%mod)%mod)%mod;

      printf("%lld\n",ans);

      return ;

}