P3240 [HNOI2015]实验比较

    • 189通过
    • 456提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 并查集 数论,数学 2015 湖南
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小D 被邀请到实验室,做一个跟图片质量评价相关的主观实验。实验用到的图片集一共有 $N$ 张图片,编号为 $1$ 到 $N$。实验分若干轮进行,在每轮实验中,小 D会被要求观看某两张随机选取的图片, 然后小D 需要根据他自己主观上的判断确定这两张图片谁好谁坏,或者这两张图片质量差不多。 用符号”$<$“、”$>$“和”$=$“表示图片 $x$和$y$($x$、$y$为图片编号)之间的比较:

    如果上下文中 $x$ 和 $y$ 是图片编号,则 $x<y$ 表示图片 $x$”质量优于“$y$,$x>y$ 表示图片 $x$”质量差于“$y$,$x=y$表示图片 $x$和 $y$”质量相同“;

    也就是说,这种上下文中,”$<$“、”$>$“、”$=$“分别是质量优于、质量差于、质量相同的意思;在其他上下文中,这三个符号分别是小于、大于、等于的含义。图片质量比较的推理规则(在 x和y是图片编号的上下文中):

    (1)$x < y$等价于 $y > x$。

    (2)若 $x < y$ 且$y = z$,则$x < z$。

    (3)若$x < y$且 $x = z$,则 $z < y$。

    (4)$x=y$等价于 $y=x$。

    (5)若$x=y$且 $y=z$,则$x=z$。

    实验中,小 D 需要对一些图片对$(x, y)$,给出 $x < y$ 或 $x = y$ 或 $x > y$ 的主观判断。小D 在做完实验后, 忽然对这个基于局部比较的实验的一些全局性质产生了兴趣。在主观实验数据给定的情形下,定义这 $N$ 张图片的一个合法质量序列为形如”$x_1$ $R_1$ $x_2$ $R_2$ $x_3$ $R_3$ $...$ $x_{N-1}$ $R_{N-1}$ $x_N$“的串,也可看作是集合$\{ x_i$ $R_i$ $x_{i+1}$ $|1\leq i\leq N-1\}$,其中 $x_i$为图片编号,$x_1$,$x_2$,...,$x_N$两两互不相同(即不存在重复编号),$R_i$为$<$或$=$,”合法“是指这个图片质量序列与任何一对主观实验给出的判断不冲突。

    例如: 质量序列$3 < 1 = 2$ 与主观判断”$3 > 1,3 = 2$“冲突(因为质量序列中 $3<1$ 且$1=2$,从而$3<2$,这与主观判断中的 $3=2$ 冲突;同时质量序列中的 $3<1$ 与主观判断中的 $3>1$ 冲突) ,但与主观判断”$2 = 1$,$3 < 2$“ 不冲突;因此给定主观判断”$3>1$,$3=2$“时,$1<3=2$ 和$1<2=3$ 都是合法的质量序列,$3<1=2$ 和$1<2<3$都是非法的质量序列。由于实验已经做完一段时间了,小D 已经忘了一部分主观实验的数据。对每张图片 $i$,小 D 都最多只记住了某一张质量不比 $i$ 差的另一张图片 $K_i$。这些小 D 仍然记得的质量判断一共有 $M$ 条($0 \leq M \leq N$),其中第$i$ 条涉及的图片对为$(K_{X_i}, X_i)$,判断要么是$K_{X_i} < X_i$ ,要么是$K_{X_i} = X_i$,而且所有的$X_i$互不相同。小D 打算就以这$M$ 条自己还记得的质量判断作为他的所有主观数据。

    现在,基于这些主观数据,我们希望你帮小 D 求出这 N 张图片一共有多少个不同的合法质量序列。

    我们规定:如果质量序列中出现”$x = y$“,那么序列中交换 $x$和$y$的位置后仍是同一个序列。因此: $1<2=3=4<5$ 和$1<4=2=3<5$ 是同一个序列, $1 < 2 = 3$ 和 $1 < 3 = 2$ 是同一个序列,而$1 < 2 < 3$ 与$1 < 2 = 3$是不同的序列,$1<2<3$和$2<1<3$ 是不同的序列。由于合法的图片质量序列可能很多, 所以你需要输出答案对$10^9 + 7$ 取模的结果

    输入输出格式

    输入格式:

    第一行两个正整数$N$,$M$,分别代表图片总数和小D仍然记得的判断的条数;接下来$M$行,每行一条判断,每条判断形如“$x < y$“或者“$x = y$“。

    输出格式:

    输出仅一行,包含一个正整数,表示合法质量序列的数目对 $10^9+7$取模的结果。

    输入输出样例

    输入样例#1: 复制
    5 4
    1 < 2
    1 < 3
    2 < 4
    1 = 5
    输出样例#1: 复制
    5

    说明

    不同的合法序列共5个,如下所示:

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