2751: [HAOI2012]容易题(easy)

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1087 Solved: 477
[Submit][Status][Discuss]

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：注意要快速幂，更重要的是记得判重——样例便有所体现，我打赌要是样例没有的话得卡掉一堆人）

 /**************************************************************

     Problem:

     User: HansBug

     Language: Pascal

     Result: Accepted

     Time: ms

     Memory: kb

 ****************************************************************/

 const p=;

 var

    i,j,k,l,m,n:longint;

    a1,a2,a3,a4,tt:int64;

    a:array[..,..] of int64;

 procedure sort(l,r:longint);

           var i,j:longint;x,y,z:int64;

           begin

                i:=l;j:=r;x:=a[(l+r) div ,];y:=a[(l+r) div ,];

                repeat

                      while (a[i,]<x) or ((a[i,]=x) and (a[i,]<y)) do inc(i);

                      while (a[j,]>x) or ((a[j,]=x) and (a[j,]>y)) do dec(j);

                      if i<=j then

                         begin

                              z:=a[j,];a[j,]:=a[i,];a[i,]:=z;

                              z:=a[j,];a[j,]:=a[i,];a[i,]:=z;

                              inc(i);dec(j);

                         end;

                until i>j;

                if i<r then sort(i,r);

                if l<j then sort(l,j);

           end;

 function trans(x:int64):int64;

          begin

               if x< then x:=(x+(abs(x) div p+)*p) mod p else x:=x mod p;

          end;

 function ksm(x,y:int64):int64;

          begin

               ksm:=;

               while y> do

                     begin

                          if odd(y) then ksm:=(ksm*x) mod p;

                          x:=(x*x) mod p;

                          y:=y div ;

                     end;

          end;

 begin

      readln(n,m,l);

      if odd(n) then

         tt:=((int64(n+) div ) *int64(n)) mod p   //注意：就是这和下下行卡了我好久，记得强制转类型

      else

          tt:=((int64(n) div )*int64(n+)) mod p;

      for i:= to l do readln(a[i,],a[i,]);

      sort(,l);a[,]:=;a[,]:=;a1:=;a2:=a[,];k:=;

      for i:= to l+ do

          begin

               if (a[i,]=a[i-,]) and (a[i,]=a[i-,]) then continue;

               if a[i,]<>a[i-,] then

                  begin

                       a1:=(a1*trans(tt-a2)) mod p;

                       a2:=;inc(k);

                  end;

               a2:=(a2+a[i,]) mod p;

          end;

      a1:=(a1*ksm(tt,m-k)) mod p;

      writeln(a1);

      readln;

 end.

Easy