CF2157H

xujindong_ · 2025-11-25 10:51:42 · 题解

下面为了方便操作，把条件改成先降后升，最后反过来。

考虑一个增量法。在排列后面加一个 p_{n+1}=n+1，也就是加一个自环，让 (n,m) 变成 (n+1,m+1)。如果 p_1=n，我们可以往环里塞一个单点，也就是令 p_1=n+1,p_{n+1}=n，让 (n,m) 变成 (n+1,m)。

这启示我们用一个增量法，先跑出较小的 n 的 2000 组构造再拓展。取 n=18，不超过这个值的 O(n2^n) 暴力。这是因为当 n=19,m\leq9 时都有超过 2000 组构造。

若 n>18,n-m\geq10，我们从 (19,i) 开始拓展。若 n-m\leq 18，我们从 (19,19-(n-m)) 开始加入自环即可。否则从 (19,1) 开始拓展，因为这是一个大环，有 p_1=19，否则 p_{19}=19 就有至少两个环。先往大环里塞若干个单点，然后再塞自环即可。

若 n>18,n-m\leq9，首先排列中至少有 n-2(n-m) 个不动点。我们注意到，p_{1\sim p_1} 之间最多有一个不动点。否则，设第一个不动点是 p_i=i，则排列的谷在 p_i 之前，而 2\sim i-1 内没有足够的位置把 1\sim i-1 的数填完。因此 p_1\leq2(n-m)+1，整个排列只有 p_{1\sim p_1} 是乱的，其他都是不动点。因此我们只需要对前 2(n-m)+1 个位置暴力即可。

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int> >ans;
void solve(int n,int m){
  for(int i=0;i<1<<n&&ans.size()<2000;i+=2){
    vector<int>p;
    for(int j=n-1;j>=0;j--)if(i>>j&1)p.push_back(j);
    for(int j=0;j<n;j++)if(~i>>j&1)p.push_back(j);
    int cyc=0;
    bool vis[n]={0};
    for(int j=0;j<n;j++){
      if(vis[j])continue;
      cyc++,vis[j]=1;
      for(int k=p[j];k!=j;k=p[k])vis[k]=1;
    }
    if(cyc==m)ans.push_back(p);
  }
}
int main(){
  cin>>n>>m;
  if(n<=18)solve(n,m);
  else if(n-m<=9){
    solve(2*(n-m)+1,n-m+1);
    for(int i=0;i<ans.size();i++)while(ans[i].size()<n)ans[i].push_back(ans[i].size());
  }
  else{
    solve(19,max(19-n+m,1));
    for(int i=0;i<ans.size();i++){
      while(ans[i].size()<n)ans[i].push_back(ans[i].size());
      if(n-m>=19){
        ans[i][0]=n-m;
        for(int j=19;j<=n-m;j++)ans[i][j]--;
      }
    }
  }
  cout<<ans.size()<<'\n';
  for(int i=0;i<ans.size();i++)for(int j=n-1;j>=0;j--)cout<<n-ans[i][j]<<(j?' ':'\n');
  return 0;
}

一个有趣的事情是，如果写一个爆搜，优先往后面放，过程中算一下最终置换环数的上下界剪枝，发现直接过了。这是因为当 n 大的时候，排列后面是一段 p_i=i-1 接一段 p_i=i，搜的时候我们先尝试往右边填一个 p_i=i，然后往左边填一个数后尝试 p_i=i-1，所以可以很快搜出来。

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,p[105];
bool vis[105];
ostringstream ans;
void dfs(int l,int r){
  if(cnt>=2000)return;
  int cyc=0;
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;i++){
    if(!p[i]||vis[i])continue;
    int pos=p[i];
    vis[i]=i;
    while(pos&&pos!=i)vis[pos]=i,pos=p[pos];
    cyc+=pos==i;
  }
  if(cyc+min(r-l+1,1)>m||cyc+r-l+1<m)return;
  if(l>r){
    cnt++;
    for(int i=1;i<=n;i++)ans<<p[i]<<(i==n?'\n':' ');
    return;
  }
  p[l]=n-r+l,dfs(l+1,r),p[l]=0;
  if(l<r)p[r]=n-r+l,dfs(l,r-1),p[r]=0;
}
int main(){
  return cin>>n>>m,dfs(1,n),cout<<cnt<<'\n'<<ans.str()<<'\n',0;
}