题目详情题解（0）讨论（0）提交记录（0）

AT_abc041_d.[ABC041D] 徒競走

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有向无环图（DAG），请计算该图的拓扑排序方案数。

输入格式

第一行包含两个整数 NN 和 MM，分别表示顶点数和边数。

接下来的 MM 行，每行包含两个整数 xx 和 yy，表示存在一条从顶点 xx 指向顶点 yy 的有向边。

输出格式

输出一个整数，表示该有向无环图的拓扑排序方案数。

输入输出样例

  • 输入#1

    3 2
2 1
2 3

    输出#1

    2

  • 输入#2

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

    输出#2

    3

  • 输入#3

    16 1
1 2

    输出#3

    10461394944000

说明/提示

  • 1≤N≤161 \leq N \leq 16
  • 0≤M≤N(N−1)/20 \leq M \leq N(N-1)/2
  • 1≤x,y≤N1 \leq x, y \leq N
  • 输入保证图是有向无环图（DAG）。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页