P2220 [HAOI2012]容易题

    • 443通过
    • 1.5K提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 数论,数学 离散化 各省省选 2012 河南
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    为了使得大家高兴,小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

    说明

    样例解释

    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

    30%的数据n<=4,m<=10,k<=10

    另有20%的数据k=0

    70%的数据n<=1000,m<=1000,k<=1000

    100%的数据 n<=10^9,m<=10^9,k<=10^5,1<=y<=n,1<=x<=m

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。