题解：P16449 [XJTUPC 2026] 怪商一克拉七鲜鱼丸

Nuclear_Fish_cyq · 2026-05-11 19:32:30 · 题解

神仙题。人生首黑/ll

我们会发现这两个东西疑似不是很好搞，所以我们考虑转化一下。

从置换组成的环来看，每次交换两个数最多让环数加一，并且对于未排序任意局面都一定可以让环数加一。那么我们考虑到排序好的置换是唯一的 n 个环的置换，设置换 P 已有 p 个环，那么 P 的最小小换次数就是 n-p。

小移的本质是把一个数取出来插进任意位置，那么从前缀最大值个数的方面看，每次旋转一个区间最多让前缀最大值个数加一，对于任意未排序局面也一定可以让个数加一。同理，设置换 P 有 q 个前缀最大值，那么 P 的最小小移次数就是 n-q。

然后问题就变成了如何把前缀最大值和不动点数一起计数。

容易设计一个 DP 状态 f_{i,j,k} 代表“[1,i] 组成的置换，不动点数为 j，前缀最大值为 k”，但是发现这里的信息不足以转移。

这两个东西还是很难维护的，我们再转化一下：定义置换 P 的 F(P) 是一个满足 Q=(1234\cdots n) 不断交换 Q_i,Q_{F(P)_i}得到的新置换正好为 P 的数组。显然这是一个双射。发现 F(P) 的不动点（满足 F(P)_i=i）对应着 P 的环数，F(P) 的后缀最小值对应了 P 的前缀最大值。

我们可以得出状态 f_{i,j,k,l} 代表：后 i 个数的最小值为 j，已经有了 k 个后缀最小值，不动点数为 l 个的方案数。注意这里是后缀最小值，

采用滚动数组优化下空间，容易得出递推：

for(int i = n - 1; i >= 1; i--){
  memset(f[i % 2], 0, sizeof(f[i % 2]));
  for(int j = 1; j <= n; j++){
    for(int k = 1; k <= (n - i); k++){
      for(int l = 0; l <= (n - i); l++){
        if(!f[1 - i % 2][j][k][l]){
          continue;
        }
        for(int qwq = 1; qwq < i; qwq++){//当前a_i的取值
          if(qwq < j){//比当前最小值还小，更新最小值和后缀最小值
            f[i % 2][qwq][k + 1][l] += f[1 - i % 2][j][k][l];
            f[i % 2][qwq][k + 1][l] %= mod;
          }
          else{//大于最小值
            f[i % 2][j][k][l] += f[1 - i % 2][j][k][l];
            f[i % 2][j][k][l] %= mod;
          }
        }
        //a_i=i的情况
        if(i < j){//比当前最小值还小，更新最小值和后缀最小值
          f[i % 2][i][k + 1][l + 1] += f[1 - i % 2][j][k][l];
          f[i % 2][i][k + 1][l + 1] %= mod;
        }
        else{//大于最小值
          f[i % 2][j][k][l + 1] += f[1 - i % 2][j][k][l];
          f[i % 2][j][k][l + 1] %= mod;
        }
      }
    }
  }
}

但是容易发现这是 O(n^5) 的。我们考虑优化一下，不难发现 j 的贡献是可以前缀和处理一下的，然后就可以优化到 O(n^4)。

:::success[代码]

#include <bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define inf INT_MAX
#define linf LLONG_MAX
#define ninf INT_MIN
#define nlinf LLONG_MIN
//#define mod 998244353
#define lwbd lower_bound
#define upbd upper_bound
//#define range
using namespace std;
void read(int &x){
    cin >> x;
    return;
}
void readll(ll &x){
    cin >> x;
    return;
}void readdb(db &x){
    cin >> x;
    return;
}
ll n, mod, f[2][151][151][151], suf[151];
//如果再忘记把题目给的1~n变为0~n-1自罚20仰卧起坐
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> mod;
    for(int i = 1; i <= n; i++){
        f[n % 2][i][1][i == n] = 1;
    }
    for(int i = n - 1; i >= 1; i--){
        memset(f[i % 2], 0, sizeof(f[i % 2]));
        for(int k = 1; k <= (n - i); k++){
            for(int l = 0; l <= (n - i); l++){
                suf[n + 1] = 0;
                for(int j = n; j >= 1; j--){
                    suf[j] = (suf[j + 1] + f[1 - i % 2][j][k][l]) % mod;
                }
                for(int qwq = 1; qwq < i; qwq++){
                    f[i % 2][qwq][k + 1][l] += suf[qwq + 1];
                    f[i % 2][qwq][k + 1][l] %= mod;
                }
                f[i % 2][i][k + 1][l + 1] += suf[i + 1];
                f[i % 2][i][k + 1][l + 1] %= mod;
            }
        }
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= (n - i); k++){
                for(int l = 0; l <= (n - i); l++){
                    if(!f[1 - i % 2][j][k][l]){
                        continue;
                    }
                    ll val = f[1 - i % 2][j][k][l];
                    if(j <= i - 1){
                        f[i % 2][j][k][l] += val * (i - j);
                        f[i % 2][j][k][l] %= mod;
                    }
                    if(i >= j){
                        f[i % 2][j][k][l + 1] += val;
                        f[i % 2][j][k][l + 1] %= mod;
                    }
                }
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            ll dsa = 0;
            for(int k = 1; k <= n; k++){
                dsa += f[1][k][n - i][n - j];
            }
            cout << dsa % mod << " ";
        }
        cout << endl;
    }
    return (0 - 0);
}

:::

upd：

观察样例可以发现这个矩阵是对称的，试图证一下。我们构建如下双射：

对于排列 P ，拆出所有置换环。例如对于 P=(624531)，得到 (16)(2)(435)。
将每个环的最大值拉到最前面，例如此时得到 (61)(2)(543)。
环之间按最大值从小到大排序，然后去除所有中间的括号。得到新置换 F(P)=(254361)。

这个东西显然是双射，所以有答案的对称性。所以小移小换不用吵架了，好耶！