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

sheepchat · 2026-05-13 11:03:15 · 题解

这题真神了。妙得不得了。

好的先看两个操作的在干嘛。

交换一次操作可以把两个置换环合一起，或者将一个置换环分开。

小换的操作最小操作次数为 n-\small\text{置换环数}。

将一个数提前最多可以多一个前缀最大值。所以

小移的操作最小操作次数为 n-\small\text{前缀最大值个数}。

现在考虑计数 P_{i,j} 为前缀最大值个数为 i，置换环个数为 j 的排列数。

现在这里有个神必转换：

考虑在排列 a 和满足 b_i\le i 的数列 b 建立双射。

具体地数列 b 可以这样映射到 i。

有 a_i=i，从 1 到 n 执行将 a_{i} 和 a_{b_i} 交换的操作。

最后得到的 a 就是数列 b 映射到的排列。

显然的，满足 b_i=i 的位置数就是置换环数。

严格后缀最小值数就是前缀最大值数。

然后计数这两个东西是简单的。

具体地计 dp_{i,j,k,l} 为目前放了后 i 到 n，最小值为 j，有 k 个严格后缀最小值，l 个位置满足 b_i=i。

枚举放的数 p\in [1,i) 可以这样转移：

可以对着 j 做差分优化。O(n^4) 通过。

#include<bits/stdc++.h>
using namespace std;
long long dp[2][155][155][155];
long long ans[155][155];
int n,mod;
int main(){
    cin>>n>>mod;
    dp[0][n+1][0][0]=1;
    bool T=0;
    for(int i=n;i>=1;i--){
        memset(dp[T^1],0,sizeof(dp[T^1]));
        for(int j=1;j<=i+1;j++){
            for(int k=0;k<=n-i;k++){
                for(int l=0;l<=n-i;l++){
                    if(dp[T][j][k][l]==0)continue;
                    if(1<=min(i-1,j-1)){
                        dp[T^1][1][k+1][l]+=dp[T][j][k][l];
                        dp[T^1][min(i-1,j-1)+1][k+1][l]-=dp[T][j][k][l];
                    }
                    if(j<=i-1){
                        dp[T^1][j][k][l]+=(i-j)*dp[T][j][k][l]%mod;
                        dp[T^1][j+1][k][l]-=(i-j)*dp[T][j][k][l]%mod;
                    }
                    if(i<j)dp[T^1][i][k+1][l+1]+=dp[T][j][k][l];
                    else {dp[T^1][j][k][l+1]+=dp[T][j][k][l];dp[T^1][j+1][k][l+1]-=dp[T][j][k][l];}
                }
            }
        }
        T^=1;
        for(int j=1;j<=i;j++){
            for(int k=0;k<=n-i+1;k++){
                for(int l=0;l<=n-i+1;l++){dp[T][j][k][l]=(dp[T][j][k][l]+dp[T][j-1][k][l])%mod;}//cout<<j<<" "<<k<<" "<<l<<" "<<dp[T][j][k][l]<<'\n';}
            }
        }
    }
    for(int k=1;k<=n;k++){
        for(int l=1;l<=n;l++){
            ans[n-k][n-l]=(dp[T][1][k][l]%mod+mod)%mod;
        }
    }
    for(int k=0;k<n;k++){
        for(int l=0;l<n;l++){
            cout<<ans[k][l]<<" ";
        }
        cout<<'\n';
    }
    return 0;
}