题解：P17132 [ICPC 2025 Shanghai R] Yet another permutation problem

· · 题解

一道水题

考虑采用区间动态规划，任意分割等价拆成多段独立区间，每段仅两种形态：原样、交换本段最大最小值。一组记录区间不拆分的形态数量，一组记录区间随意拆分的总方案。按区间由短到长计算，枚举分割位置合并左右方案，各段组合数相乘累加。仅最值位置可互换，其余数字顺序不变，最终完整区间全拆分总方案即为答案。

代码配有注释，请享用~

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353,MOD=998244353;
const int N=505,M=5000010,Q=5010;
int a[N],b[N];
int f[N][N][3],g[N][N][3];
inline int add(int x,int y){
    return x+y>=mod?x+y-mod:x+y;
}
inline int sub(int x,int y){
    return x>=y?x-y:x+mod-y;
}
void inc(int &x,int y){
    x=(x+y)%mod;
}
void dec(int &x,int y){
    x=(x-y+mod)%mod;
}
int findmn(int l,int r){
    int pos=0;
    for(int i=l;i<=r;i++)
        if(!pos||b[i]<b[pos]) pos=i;
    return pos;
}
int findmx(int l,int r){
    int pos=0;
    for(int i=l;i<=r;i++)
        if(!pos||b[i]>b[pos]) pos=i;
    return pos;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    // 单点初始化
    for(int i=1;i<=n;i++){
        f[i][i][0]=f[i][i][1]=f[i][i][2]=1;
        g[i][i][0]=g[i][i][1]=g[i][i][2]=1;
    }
    // 区间DP，按长度从小到大
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            for(int i=l;i<=r;i++) b[i]=a[i];
            int p=findmn(l,r),q=findmx(l,r);
            // 计算f[l][r][0]
            f[l][r][0]=0;
            if(p<q){
                for(int i=p;i<=q-1;i++)
                    inc(f[l][r][0],1ll*f[l][i][1]*g[i+1][r][2]%mod);
                for(int i=q;i<=r-1;i++)
                    dec(f[l][r][0],1ll*f[l][i][0]*g[i+1][r][0]%mod);
            }else{
                for(int i=q;i<=p-1;i++)
                    inc(f[l][r][0],1ll*f[l][i][2]*g[i+1][r][1]%mod);
                for(int i=p;i<=r-1;i++)
                    dec(f[l][r][0],1ll*f[l][i][0]*g[i+1][r][0]%mod);
            }
            // f[l][r][1]：交换后min位置变成原max
            b[p]=n;
            int x=findmn(l,r);
            f[l][r][1]=0;
            if(x<p){
                for(int i=x;i<=p-1;i++)
                    inc(f[l][r][1],1ll*f[l][i][1]*g[i+1][r][0]%mod);
                for(int i=p;i<=r-1;i++)
                    dec(f[l][r][1],1ll*f[l][i][1]*g[i+1][r][0]%mod);
            }else{
                for(int i=p;i<=x-1;i++)
                    inc(f[l][r][1],1ll*f[l][i][0]*g[i+1][r][1]%mod);
                for(int i=x;i<=r-1;i++)
                    dec(f[l][r][1],1ll*f[l][i][1]*g[i+1][r][0]%mod);
            }
            b[p]=a[p];
            // f[l][r][2]：交换后max位置变成原min
            b[q]=1;
            int y=findmx(l,r);
            f[l][r][2]=0;
            if(q<y){
                for(int i=q;i<=y-1;i++)
                    inc(f[l][r][2],1ll*f[l][i][0]*g[i+1][r][2]%mod);
                for(int i=y;i<=r-1;i++)
                    dec(f[l][r][2],1ll*f[l][i][2]*g[i+1][r][0]%mod);
            }else{
                for(int i=y;i<=q-1;i++)
                    inc(f[l][r][2],1ll*f[l][i][2]*g[i+1][r][0]%mod);
                for(int i=q;i<=r-1;i++)
                    dec(f[l][r][2],1ll*f[l][i][2]*g[i+1][r][0]%mod);
            }
            b[q]=a[q];
            // g[l][r] = 合并所有分块的总方案
            g[l][r][0]=f[l][r][0];
            g[l][r][1]=f[l][r][1];
            g[l][r][2]=f[l][r][2];
            for(int i=l;i<=r-1;i++)
                inc(g[l][r][0],1ll*f[l][i][0]*g[i+1][r][0]%mod);
            for(int i=l;i<=p-1;i++)
                inc(g[l][r][1],1ll*f[l][i][0]*g[i+1][r][1]%mod);
            for(int i=p;i<=r-1;i++)
                inc(g[l][r][1],1ll*f[l][i][1]*g[i+1][r][0]%mod);
            for(int i=l;i<=q-1;i++)
                inc(g[l][r][2],1ll*f[l][i][0]*g[i+1][r][2]%mod);
            for(int i=q;i<=r-1;i++)
                inc(g[l][r][2],1ll*f[l][i][2]*g[i+1][r][0]%mod);
        }
    }
    cout<<g[1][n][0]<<'\n';
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

通过记录