Description
Input
Output
输出仅一行，包含一个正整数，表示合法质量序列的数目对 10^9+7取模的结果。
Sample Input
1 < 2
1 < 3
2 < 4
1 = 5
Sample Output
HINT
不同的合法序列共5个，如下所示：
题解
做之前偷瞄了一眼标签，想的时候就直接往上靠了，并不是很难想。
首先一个值得肯定的条件就是，如果出现 $u$ '=' $v$ ，显然 $u$ 和 $v$ 可以缩成一个点。用并查集辅助。
若我们将 $u$ '<' $v$ 看成是一条 $u->v$ 的有向边，注意到题目说的对于每个点，只有一个“前驱”（缩点后也只有一个前驱），所以说如何合法的话这些节点和边构成了一些树形图的森林。
我们建立 $0$ 节点，来使森林联通，遍历整棵树，除去不合法的情况。
现在问题就变成了给你一棵树，让你生成一个包含所有数且两个数之间用 '=' 或 '<' 号连接的序列。保证父亲总比儿子先在序列中出现，同一棵子树的内部用 '<' 连接；不同儿子的子树间用 '=' 或 '<' 连接。问方案数。
考虑这样一个问题：若只能用 '<' 连接。这个问题将极度简化，我们记 $f_u$ 表示在以 $u$ 节点为根的子树中的方案数。$f_u$ 可起到临时存中间变量的作用。
枚举儿子节点 $v$ 的时候，我们用 $tol$ 表示已处理过的子树的总大小： $$f_u = f_u*f_v*C_{tol+f_v}^{f_v}$$
现在考虑原问题。由于子树间的等号关系不好处理，我们可以将其放到状态中，我们记 $f_{u, k}$ 为在以 $u$ 为根的子树中生成的序列含有 $k$ 个 '<' 的方案数。
现在我们还是考虑 $dp$ 。
假设已处理过的子树总 $size$ 为 $a$ ，记录下来的 $dp$ 值存在 $p_i$ 中，正在处理的子树的 $size$ 为 $b$ ，记录下来的 $dp$ 值存在 $q_i$ 中。
由题，合并后的 '<' 的个数介于 $max(a, b)$ 和 $a+b$ 之间。
我们枚举 $i <= a, j <= b$，同理合并后的 '<' 的个数介于 $max(i, j)$ 和 $i+j$ 之间。现在相当于将 $i$ 个白球， $j$ 个黑球放入 $k$ 个盒子中，且同个盒子不能有相同颜色的球，盒子不能空。
$$f_{u, k} += \sum_{i = 1}^a \sum_{j = 1}^b p_i*q_j*C_k^i*C_i^{j-(k-i)}$$
其中 $C_k^i$ 表示在 $k$ 个盒子中选出 $i$ 个放白球，因为所有盒子都要放球，所以剩下的 $k-i$ 个盒子必定放黑球，剩下 $j-(k-i)$ 个黑球要放在 $i$ 个放白球的盒子中。
//It is made by Awson on 2018.1.2
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define LD long double
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
const int N = ;
const int MOD = 1e9+; int fa[N+], n, m, pre[N+], u, v, vis[N+], rt[N+], C[N+][N+], f[N+][N+], size[N+];
char ch[];
struct tt {
int to, next;
}edge[N+];
int path[N+], top; int find(int r) {
return fa[r] ? fa[r] = find(fa[r]) : r;
}
void add(int u, int v) {
edge[++top].to = v;
edge[top].next = path[u];
path[u] = top;
}
void dfs(int u) {
int g[N+], flag = ;
for (int I = path[u]; I; I = edge[I].next) {
memset(g, , sizeof(g)); dfs(edge[I].to);
if (flag) {
for (int i = ; i <= size[u]; i++)
if (f[u][i])
for (int j = ; j <= size[edge[I].to]; j++)
if (f[edge[I].to][j])
for (int k = Max(i, j); k <= i+j; k++)
g[k] = (g[k]+(LL)f[u][i]*f[edge[I].to][j]%MOD*C[k][i]%MOD*C[i][j-(k-i)]%MOD)%MOD;
size[u] += size[edge[I].to];
for (int i = ; i <= size[u]; i++) f[u][i] = g[i];
}else {
flag = , size[u] += size[edge[I].to];
for (int i = ; i <= size[u]; i++) f[u][i] = f[edge[I].to][i];
}
}
if (!flag) f[u][] = ;
++size[u];
for (int i = size[u]; i; i--) f[u][i] = f[u][i-];
}
bool judge(int u) {
if (vis[u]) return false; vis[u] = ;
for (int i = path[u]; i; i = edge[i].next) if (!judge(edge[i].to)) return false;
return true;
}
void work() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) {
C[i][] = ;
for (int j = ; j <= i; j++) C[i][j] = (C[i-][j-]+C[i-][j])%MOD;
}
for (int i = ; i <= m; i++) {
scanf("%d%s%d", &u, ch, &v);
if (ch[] == '=') {
int p = find(u), q = find(v);
if (p != q) fa[p] = q, rt[p] = , pre[q] = Max(pre[q], pre[p]);
}else pre[v] = u;
}
for (int i = ; i <= n; i++) if (!rt[i]) add(find(pre[i]), i);
for (int i = ; i <= n; i++) if (!vis[i]) if (!judge(i)) {printf("0\n"); return; }
dfs();
int ans = ;
for (int i = ; i <= size[]; i++) ans = (ans+f[][i])%MOD;
printf("%d\n", ans);
}
int main() {
work();
return ;
}