意甲冠军：

序列p1、p2、p3……pn由1、2、3……n这些数字  现在给出一些条件pi<pj  部条件的排列的个数

思路：

非常easy想到用一条有向的线连接全部的pi和pj  那么就构成了有向无环图（题中说有解所以无环）

又由于pi各不同样  那么题目就变成了有向无环图的拓扑排序的种类数

题目中边数较少  所以可能出现不连通情况  我们先讨论一个连通集合内拓扑排序的种类数

题目中m较小  能够利用状压后的记忆化搜索解决

如今考虑假设知道了A和B两个集合各自的种类数  假设把它们合起来

因为各自种类已知  我们能够把A和B当成有序的排列  那么问题就变成了将|B|个元素插空到|A|个元素中间

这个能够利用dp解决  同一时候n较小  我们能够直接打出表

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 45typedef long long LL;const int mod = (int) 1e9 + 7;int dp[2][N], f[N][N], in[N], out[N], fa[N], vis[N], qu[N], g[1 << 21];vector
         
           ed[N];int n, m, ans, top;struct node { int id, fa; bool operator<(const node ff) const { return fa < ff.fa; }} nd[N];void init() { for (int i = 1; i <= n; i++) { in[i] = out[i] = 0; fa[i] = i; vis[i] = 0; ed[i].clear(); } ans = 1; top = 0;}int getf(int x) { if (x != fa[x]) fa[x] = getf(fa[x]); return fa[x];}LL topo(int sta) { if (g[sta] != -1) return g[sta]; LL res = 0; int i, u, j, ss; for (i = 0; i < top; i++) { u = qu[i]; if (!vis[u] && !in[u]) { vis[u] = 1; ss = ed[u].size(); for (j = 0; j < ss; j++) in[ed[u][j]]--; res += topo(sta | (1 << i)); vis[u] = 0; for (j = 0; j < ss; j++) in[ed[u][j]]++; } } return g[sta] = res % mod;}void maketable() { int i, j, u, v, from, to; for (i = 1; i < N; i++) { f[0][i] = 1; for (j = i; j < N; j++) { for (v = 1; v <= i + 1; v++) dp[1][v] = 1; to = 1; for (u = 2; u <= j; u++) { from = (u & 1) ^ 1; to = u & 1; for (v = 1; v <= i + 1; v++) dp[from][v] = (dp[from][v] + dp[from][v - 1]) % mod; for (v = 1; v <= i + 1; v++) dp[to][v] = dp[from][v]; } for (v = 1; v <= i + 1; v++) dp[to][v] = (dp[to][v] + dp[to][v - 1]) % mod; f[j][i] = f[i][j] = dp[to][i + 1]; } }}int main() { int i, j, u, v; maketable(); while (~scanf("%d%d", &n, &m)) { init(); for (i = 1; i <= m; i++) { scanf("%d%d", &u, &v); if (u == v) continue; ed[u].push_back(v); in[v]++; out[u]++; u = getf(u); v = getf(v); if (u != v) fa[v] = u; } for (i = 1; i <= n; i++) { nd[i].id = i; nd[i].fa = getf(i); } sort(nd + 1, nd + n + 1); nd[n + 1].fa = -1; for (i = 1; i <= n; i = j) { top = 1; qu[0] = nd[i].id; for (j = i + 1; j <= n + 1; j++) { if (nd[j].fa == nd[i].fa) { qu[top++] = nd[j].id; } else { for (u = 0; u < (1 << top); u++) g[u] = -1; g[(1 << top) - 1] = 1; ans = (LL) ans * (topo(0) * f[i - 1][j - i] % mod) % mod; break; } } } printf("%d\n", ans); } return 0;}