Description：

给一些等于或者小于关系，求有几种拓扑序，相等的交换位置算一种。

$1\leqslant n\leqslant 100$

Solution：

首先把等于的点缩起来，最后一定是一棵树，于是我们可以使用树形 $DP$ 来解决：

Solution1：

我们考虑把点 $k$ 和他的子树 $v$ 合并，如果不考虑相等的算一种的话那就直接用一个组合数分配就行了，但是相等的交换顺序算一种，因此我们设 $f[i][j]$ 表示到了点 $i$ ，子树内有 $j$ 种不同的值的方案数，设现在在根的位置有 $j$ 个值，子树内有 $j'$ 个值，最后和出了 $i$ 个值，那么显然有 $\max(j,j'+1)\leqslant i\leqslant j+j'$ ，首先 $k$ 那个点肯定是最小的，也就是说还剩 $i-1$ 个位置，然后把 $k$ 原来的点放进去，有 $\binom{i-1}{j-1}$ 种方案，再考虑子树中的权值，他们必须把那 $i-j$ 个还空着的位置填满，然后还有 $j'-(i-j)$ 个，他们应该和那 $j-1$ 个合并，也就是 $\binom{j-1}{j'-(i-j)}$ 。

Code1：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

inline char getc()

{

	register char c = getchar();

	while(c != '<' && c != '=')c = getchar();

	return c;

}

int n,m;

#define MAXN 110

int f[MAXN];

int find(int x){return (f[x] == 0 ? x : f[x] = find(f[x]));}

int ind[MAXN];

struct edges

{

	int a,b;

}es[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{//cout << a << " -> " << b << endl;

	++ind[b];

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int C[MAXN][MAXN];

#define MOD 1000000007

int g[MAXN][MAXN];

int tmp[MAXN];

int siz[MAXN];

void dp(int k)

{

	g[k][1] = 1;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		dp(e[i].to);

		memcpy(tmp,g[k],sizeof(tmp));

		memset(g[k],0,sizeof(g[k]));

		for(int j = 1;j <= siz[k];++j)

		{

			for(int j_ = 1;j_ <= siz[e[i].to];++j_)

			{

				for(int x = max(j,j_ + 1);x <= j + j_;++x)

				{//cout << x << " " << j << " " << j_ << " : " << tmp[j] << " " << g[e[i].to][j_] << " " << C[x - 1][j - 1] << " " << C[j - 1][j_ - (x - j)] << endl;

					g[k][x] = (g[k][x] + 1ll * tmp[j] * g[e[i].to][j_] % MOD * C[x - 1][j - 1] % MOD * C[j - 1][j_ - (x - j)] % MOD) % MOD;

				}

			}

		}

		siz[k] += siz[e[i].to];

	}

	//cout << k << " : ";for(int i = 1;i <= siz[k];++i)cout << g[k][i] << " ";cout << endl;

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	C[0][0] = 1;

	for(int i = 1;i <= n;++i)

	{

		C[i][0] = 1;

		for(int j = 1;j <= i;++j)C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;

	}

	for(int i = 1;i <= m;++i)

	{

		es[i].a = rd();

		char ch = getc();

		es[i].b = rd();

		if(ch == '=')

		{

			int p = find(es[i].a),q = find(es[i].b);

			if(p == q)continue;

			else f[p] = q;

			es[i].a = es[i].b = 0;

		}

	}

	for(int i = 1;i <= m;++i)

	{

		if(es[i].a != 0)add(find(es[i].a),find(es[i].b));

	}

	for(int i = 1;i <= n;++i)

	{

		if(find(i) == i && ind[i] == 0)add(0,i);

	}

	dp(0);

	for(int i = 1;i <= n;++i)

	{

		if(find(i) == i && siz[i] == 0)

		{

			puts("0");

			return 0;

		}

	}

	int ans = 0;

	for(int i = 0;i <= n + 1;++i)ans = (ans + g[0][i]) % MOD;

	cout << ans << endl;

	return 0;

}

Solution2：

还是设 $h[i]$ 表示用 $1\sim i$ 给 $n$ 个人随意分配标号的方案数， $g[i]$ 表示用 $1\sim i$ 给 $n$ 个人分配合法的标号，也就是说每个标号都至少分给一个人的方案数，那么有： $$ h[i]=\sum_{j=0}^i\binom ij g[j] $$ 二项式反演得： $$ g[i]=\sum_{j=0}^i\binom ij(-1)^{i-j}h[j] $$ 那么如果我们能求 $h$ ，就能反过来求 $g$ ， $h$ 比较好求，转移为： $$ h[k][i]=\prod h[v][i-1] $$ 也就是说只要根节点与子树不同就行了，不一定非得要所有编号都用上， $DP$ 和反演都是 $O(n^2)$ 得。

Code2：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

    register int res = 0,f = 1;register char c = getchar();

    while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

    while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

    return res * f;

}

inline char getc()

{

    register char c = getchar();

    while(c != '<' && c != '=')c = getchar();

    return c;

}

int n,m;

#define MAXN 110

int f[MAXN];

int find(int x){return (f[x] == 0 ? x : f[x] = find(f[x]));}

int ind[MAXN];

struct edges

{

    int a,b;

}es[MAXN];

struct edge

{

    int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{//cout << a << " -> " << b << endl;

    ++ind[b];

    e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

    return;

}

int C[MAXN][MAXN];

#define MOD 1000000007

int g[MAXN][MAXN];

bool vis[MAXN];

void dp(int k)

{

    vis[k] = true;

    for(int i = 1;i <= n + 1;++i)g[k][i] = 1;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        dp(e[i].to);

        for(int x = 1;x <= n + 1;++x)g[k][x] = 1ll * g[k][x] * g[e[i].to][x - 1] % MOD;

    }

    for(int i = 1;i <= n + 1;++i)g[k][i] = (g[k][i] + g[k][i - 1]) % MOD;

    return;

}

int main()

{

    scanf("%d%d",&n,&m);

    C[0][0] = 1;

    for(int i = 1;i <= n + 1;++i)

    {

        C[i][0] = 1;

        for(int j = 1;j <= i;++j)C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;

    }

    for(int i = 1;i <= m;++i)

    {

        es[i].a = rd();

        char ch = getc();

        es[i].b = rd();

        if(ch == '=')

        {

            int p = find(es[i].a),q = find(es[i].b);

            if(p == q)continue;

            else f[p] = q;

            es[i].a = es[i].b = 0;

        }

    }

    for(int i = 1;i <= m;++i)

    {

        if(es[i].a != 0)add(find(es[i].a),find(es[i].b));

    }

    for(int i = 1;i <= n;++i)

    {

        if(find(i) == i && ind[i] == 0)add(0,i);

    }

    dp(0);

    for(int i = 1;i <= n;++i)

    {

        if(find(i) == i && !vis[i])

        {

            puts("0");

            return 0;

        }

    }

    int ans = 0;

    for(int i = 1;i <= n + 1;++i)

    {

        for(int j = 1;j <= i;++j)

        {

            if((i - j) & 1)ans = (ans - 1ll * g[0][j] * C[i][j] % MOD + MOD) % MOD;

            else ans = (ans + 1ll * g[0][j] * C[i][j] % MOD) % MOD;

        }

    }

    cout << ans << endl;

    return 0;

}