2751: [HAOI2012]容易题(easy)
2751: [HAOI2012]容易题(easy)
2751: [HAOI2012]容易题(easy)
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1087 Solved: 477
Description
为了使得大家高兴，小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 样例解释 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
HINT
数据范围 30%的数据n<=4,m<=10,k<=10 另有20%的数据k=0 70%的数据n<=1000,m<=1000,k<=1000 100%的数据 n<=109,m<=109,k<=105,1<=y<=n,1<=x<=m
Source
（Tip：唉。。。为了倒霉的期中考试，好久没编程了，果然逗比频频）
题解：题目说是简单题，实际上这真的不是神犇卖萌，真的比较水（HansBug：As For 省选题），但是我WAWAWA狂WA不止，结果发现居然是卡数据类型了TT，表示一万个逗比= =。。。实际上题目的思路很明显，就是将各个位置上面被Ban掉的数减掉，然后求积就好啦（HansBug：注意要快速幂，更重要的是记得判重——样例便有所体现，我打赌要是样例没有的话得卡掉一堆人）
1 /**************************************************************
2 Problem: 2751
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:448 ms
7 Memory:3352 kb
8 ****************************************************************/
9
10 const p=1000000007;
11 var
12 i,j,k,l,m,n:longint;
13 a1,a2,a3,a4,tt:int64;
14 a:array[0..200000,1..2] of int64;
15 procedure sort(l,r:longint);
16 var i,j:longint;x,y,z:int64;
17 begin
18 i:=l;j:=r;x:=a[(l+r) div 2,1];y:=a[(l+r) div 2,2];
19 repeat
20 while (a[i,1]<x) or ((a[i,1]=x) and (a[i,2]<y)) do inc(i);
21 while (a[j,1]>x) or ((a[j,1]=x) and (a[j,2]>y)) do dec(j);
22 if i<=j then
23 begin
24 z:=a[j,1];a[j,1]:=a[i,1];a[i,1]:=z;
25 z:=a[j,2];a[j,2]:=a[i,2];a[i,2]:=z;
26 inc(i);dec(j);
27 end;
28 until i>j;
29 if i<r then sort(i,r);
30 if l<j then sort(l,j);
31 end;
32 function trans(x:int64):int64;
33 begin
34 if x<0 then x:=(x+(abs(x) div p+1)*p) mod p else x:=x mod p;
35 end;
36 function ksm(x,y:int64):int64;
37 begin
38 ksm:=1;
39 while y>0 do
40 begin
41 if odd(y) then ksm:=(ksm*x) mod p;
42 x:=(x*x) mod p;
43 y:=y div 2;
44 end;
45 end;
46 begin
47 readln(n,m,l);
48 if odd(n) then
49 tt:=((int64(n+1) div 2) *int64(n)) mod p //注意：就是这和下下行卡了我好久，记得强制转类型
50 else
51 tt:=((int64(n) div 2)*int64(n+1)) mod p;
52 for i:=1 to l do readln(a[i,1],a[i,2]);
53 sort(1,l);a[0,1]:=0;a[0,2]:=0;a1:=1;a2:=a[1,2];k:=0;
54 for i:=2 to l+1 do
55 begin
56 if (a[i,1]=a[i-1,1]) and (a[i,2]=a[i-1,2]) then continue;
57 if a[i,1]<>a[i-1,1] then
58 begin
59 a1:=(a1*trans(tt-a2)) mod p;
60 a2:=0;inc(k);
61 end;
62 a2:=(a2+a[i,2]) mod p;
63 end;
64 a1:=(a1*ksm(tt,m-k)) mod p;
65 writeln(a1);
66 readln;
67 end.