题目链接：

题意：问有多少个 1 到 n 的排列，使得用给定的 k 个比较器（使 au 和 av 有序）排序后，整个序列的最长上升子序列为 n - 1。

题解：先处理出全部最长上升子序列为 n - 1 的排列，然后枚举每个比较器使用与否，计数即可。（题目卡常，dfs要加引用...）

 

1 #include 
     
       2 using namespace std; 3 #define ll long long 4 #define ull unsigned long long 5 #define mst(a,b) memset((a),(b),sizeof(a)) 6 #define mp(a,b) make_pair(a,b) 7 #define pi acos(-1) 8 #define pii pair
      
        9 #define pb push_back10 const int INF = 0x3f3f3f3f;11 const double eps = 1e-6;12 const int maxn = 1e6 + 10;13 const int maxm = 1e5 + 10;14 //const ll mod =  998244353;15 16 set
       
        
         >se;17 int a[55],u[15],v[15];18 19 int dfs(vector
         
          &vec,int now) {20     if(now < 0) return 1;21     int l = u[now], r = v[now], ans = 0;22     if(vec[l] < vec[r]) {23         ans += dfs(vec,now - 1);24         swap(vec[l],vec[r]);25         ans += dfs(vec,now - 1);26         swap(vec[l],vec[r]);27     }28     return ans;29 }30 31 int main() {32 #ifdef local33     freopen("data.txt", "r", stdin);34 //    freopen("data.txt", "w", stdout);35 #endif36     for(int i = 0; i < 55; i++) a[i] = i;37     int t;38     scanf("%d",&t);39     while(t--) {40         se.clear();41         int n,k,mod;42         scanf("%d%d%d",&n,&k,&mod);43         for(int i = 0; i < k; i++) {44             scanf("%d%d",&u[i],&v[i]);45             u[i]--, v[i]--;46         }47         int ans = 0;48         for(int i = 0; i < n; i++) {49             vector
          
           vec;50 for(int j = 0; j < i; j++) vec.push_back(j);51 for(int j = i + 1; j < n; j++) vec.push_back(j);52 for(int j = 0; j < n; j++) {53 vector
           
            v;54 for(int k = 0; k < j; k++) v.push_back(vec[k]);55 v.push_back(i);56 for(int k = j; k < vec.size(); k++) v.push_back(vec[k]);57 if(se.find(v) == se.end()) ans += dfs(v,k - 1);58 se.insert(v);59 }60 }61 printf("%d\n",ans % mod);62 }63 return 0;64 }