2751: [HAOI2012]容易题(easy)

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

 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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

2761: [JLOI2011]不重复数字(平衡树)

2761: [JLOI2011]不重复数字 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2133  So...

2765
来自专栏算法修养

Code Forces 652C Foe Pairs

C. Foe Pairs time limit per test 1 second memory limit per test 256 megaby...

3338
来自专栏算法修养

HDU 1403 Eight&POJ 1077(康拖,A* ,BFS,双广)

Eight Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Ja...

3057
来自专栏ACM算法日常

String Problem(KMP+最小表示法)- HDU 3374

Give you a string with length N, you can generate N strings by left shifts. For ...

792
来自专栏友弟技术工作室

golang之Struct什么是结构体struct?

最近在复习golang,学习的东西,如果不使用,很快就会忘记。所以,准备复习完golang,做一个练手的小项目,加深对golang的学习。今天开始公司,进入封闭...

5766
来自专栏算法修养

POJ-2329 Nearest number - 2(BFS)

Nearest number - 2 Time Limit: 5000MS Memory Limit: 65536K Total Submis...

2444
来自专栏ml

uva------(11464)Even Parity

D Even Parity Input: Standard Input Output: Standard Output We...

3676
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第10章 Kotlin与Java互操作

在前面的章节中,我们已经学习了Kotlin的基础语法、类型系统、泛型与集合类、面向对象与函数式编程等主题,在上一章中我们还看到了Kotlin提供的轻量级并发编程...

1802
来自专栏進无尽的文章

编码篇 - 正则表达式及其相关

有时我们需要在一大段长文本中过滤出我们需要的字段,或者检验该文本是否符合要求(该文本是否是邮箱,链接,电话号码或身份证),这时候就需要用到正则表达式了,当然我们...

1102
来自专栏java初学

spring框架(3)— spring集合类的注入

1153

扫码关注云+社区

领取腾讯云代金券