题目描述

题解

考虑到最后的序列为 $(n-1{)}^2+1$ 个，所以直接枚举每个排序器有没有生效即可。效率： $O(n^2\times 2^k)$ 。

考虑正确性，一个序列经过 $k$ 个操作后只能变成另一个序列，所以能够得到某个序列的初始序列的集合是不会重复的，所以直接做就好了。

代码

#include<bits/stdc++.h>
using namespace std;
int T,n,m,P,s,p[55],U[15],V[15];
void dfs(int x){if (!x){s++;return;}if (p[U[x]]>p[V[x]]) return;dfs(x-1);swap(p[U[x]],p[V[x]]);dfs(x-1);swap(p[U[x]],p[V[x]]);
}
void work(){scanf("%d%d%d",&n,&m,&P);s=0;for (int i=1;i<=m;i++)scanf("%d%d",&U[i],&V[i]);for (int i=1;i<=n;i++) p[i]=i;dfs(m);for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (j==i || j==i-1) continue;p[j]=i;for (int k=1,l=1;k<=n;k++){if (k==j) continue;if (l==i) l++;p[k]=l++;}dfs(m);}}printf("%d\n",s);
}
int main(){for (scanf("%d",&T);T--;work());return 0;
}