← 返回题目列表

AtCoder · agc016_f

F. DAG 上的游戏

中文机器翻译题面 查看原题

分数: 1600 点

问题陈述

有一个有向图 G 与 N 顶点和 M 边缘。 顶点已编号 1 通过 N,并且边缘已编号 1 通过 M。 边缘 i 定向自 x_i to y_i。 在这里, x_i < y_i 成立。 此外,不存在重边 G.

考虑选择该集合的子集 M 边缘 G,并从 G 获取另一张图 G'。 有 2^M 不同可能的图表为 G'.

Alice 和 Bob 在以下游戏中对战 G'。 首先,将两块放在顶点上 1 和 2,每人一个。 然后,从Alice开始,Alice和Bob交替执行以下操作:

  • 选择一条边 i 使得顶点上放置了一块 x_i,并将棋子移动到顶点 y_i (如果顶点上有两块 x_i,仅移动一)。允许将两个棋子放置在同一顶点上。

当玩家无法执行操作时,他/她就输了。 我们假设两名球员都发挥最佳状态。

其中 2^M 不同可能的图表为 G',有多少导致爱丽丝获胜? 求计数模数 10^9+7.

约束

  • 2 ≤ N ≤ 15
  • 1 ≤ M ≤ N(N-1)/2
  • 1 ≤ x_i < y_i ≤ N
  • 全部 (x_i,\ y_i) 是不同的。

输入

输入由标准输入按以下格式给出:

N M
x_1 y_1
x_2 y_2
:
x_M y_M

输出

打印数量 G' 导致爱丽丝获胜,取模 10^9+7.


示例输入 1

2 1
1 2

示例输出 1

1

下图显示了两种可能的图表: G'。 标有○的图表导致爱丽丝获胜,标有×的图表导致鲍勃获胜。

b250f23c38d0f5ec2204bd714e7c1516.png

示例输入 2

3 3
1 2
1 3
2 3

示例输出 2

6

下图显示了八种可能的图表: G'.

8192fd32f894f708c5e4a60dcdea9d35.png

示例输入 3

4 2
1 3
2 4

示例输出 3

2

示例输入 4

5 10
2 4
3 4
2 5
2 3
1 2
3 5
1 3
1 5
4 5
1 4

示例输出 4

816