题目描述
为了使得大家高兴，小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 1 1 1 1 2 2 2 3 4 3
输出 #1
90
分析：
本题考虑到(a1+a2+……an)*(b1+n2+……bn)=a1*b1+a1*b2+……+an*bn，所以不难得出一条结论，即把每一位可以取到的值叠加，然后相乘就行了。但是由于n过大，所以我们需要一些优化。
CODE：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int mod=1000000007; 7 const int M=100005; 8 long long n,m,k; 9 long long ans=1; 10 struct node{ 11 long long id,val; 12 }a[M]; 13 long long sum[M]; 14 int cnt; 15 long long get(){ 16 char c=getchar(); 17 long long res=0,f=1; 18 while (c>'9'||c<'0'){ 19 if (c=='-') f=-1; 20 c=getchar(); 21 } 22 while (c<='9'&&c>='0'){ 23 res=(res<<3)+(res<<1)+c-'0'; 24 c=getchar(); 25 } 26 return res*f; 27 } 28 bool cmp(node x,node y){ 29 if (x.id==y.id) return x.val<y.val; 30 else return x.id<y.id; 31 } 32 long long poww(long long a,int b){ 33 a%=mod; 34 long long res=1; 35 while (b){ 36 if (b&1) res=res*a%mod; 37 a=a*a%mod; 38 b>>=1; 39 } 40 return res; 41 } 42 int main(){ 43 n=get(),m=get(),k=get(); 44 for (int i=1;i<=k;i++) a[i].id=get(),a[i].val=get(); 45 sort(a+1,a+k+1,cmp); 46 for (int i=1;i<=k;i++){ 47 if (a[i].id!=a[i-1].id) sum[++cnt]=n*(n+1)/2%mod; 48 else if (a[i].val==a[i-1].val) continue; 49 sum[cnt]=(sum[cnt]-a[i].val+mod)%mod; 50 } 51 ans=poww(n*(n+1)/2,m-cnt)%mod; 52 //cout<<ans<<endl; 53 for (int i=1;i<=cnt;i++) ans=(ans*sum[i]+mod)%mod; 54 cout<<ans%mod<<endl; 55 return 0; 56 }