简答题 偏难
#20619

排队 时间限制:1.0 s 内存限制:512.0 MB 题目描述 小杨所在班级共有 n 位同学,依次以 1,2,...,n 标号。这 n 位同学想排成一行队伍,…

排队

时间限制:1.0 s

内存限制:512.0 MB

题目描述

小杨所在班级共有 n 位同学,依次以 1,2,...,n 标号。这 n 位同学想排成一行队伍,其中有些同学之间关系非常好,在队伍里需要排在相邻的位置。具体来说,有 m 对这样的关系( m 是一个非负整数)。当 m≥1 时,第 i 对关系 (1≤i≤m) 给出 ai,bi,表示排队时编号为 ai的同学需要排在编号为 bi的同学前面,并且两人在队伍中相邻。

现在小杨想知道总共有多少种排队方式。由于答案可能很大,你只需要求出答案对 109+7 取模的结果。

输入格式

第一行,两个整数 n,m,分别表示同学们的数量与关系数量。

接下来 m 行,每行两个整数 ai,bi,表示一对关系。

输出格式

一行,一个整数,表示答案对 109+7 取模的结果。

输入样例 1

4 2
1 3
2 4

输出样例 1

2

输入样例 2

3 0

输出样例 2

6

输入样例 3

3 2
1 2
2 1

输出样例 3

0

数据范围

对于 20% 的测试数据点,保证 1≤n≤8,0≤m≤10 。

对于另外 20% 的测试数据点,保证 1≤n≤103,0≤m≤1 。

对于所有测试数据点,保证 1≤n≤2×105,0≤m≤2×105。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; using namespace std; const int N = 2e5 + 5; const int mod = 1e9 + 7; int n, m; int pre[N], suf[N]; int vis[N]; int cnt; int ans; int main() { scanf("%d%d", &amp;n, &amp;m); ans = 1; for (int i = 1; i &lt;= m; i++) { int a, b; scanf("%d%d", &amp;a, &amp;b); if (pre[b] == a &amp;&amp; suf[a] == b) continue; if (pre[b] || suf[a]) ans = 0; pre[b] = a; suf[a] = b; } for (int i = 1; i &lt;= n; i++) { if (vis[i]) continue; int j = i; while (j) { if (vis[j] == i) ans = 0; if (vis[j]) break; vis[j] = i; j = suf[j]; } } for (int i = 1; i &lt;= n; i++) cnt += !pre[i]; for (int i = 1; i &lt;= cnt; i++) ans = 1ll * ans * i % mod; printf("%d\n", ans); return 0; }</pre>
这道题暂未补解析。