题解：CF2249B Permutation Cuts

majingxuan123 · 2026-08-08 15:49:55 · 题解

完了，cf1700 我都差点没做出来，我该在哪里停留，我问我自己。

首先判断无解情况。

• 设 \forall i\in[l,r],a_i=n-1，且 a_{l-1}\ne n-1,a_{r+1}\ne n-1，那么 a_1\le a_2\le \dots\le a_l,a_r\ge a_{r+1}\ge\dots\ge a_{n-1},a_l=a_{l+1}=\dots=a_r=n-1。因为在 p_i=n 时，前缀最大值会超过后缀最大值。所以前期由于 i 增加，前缀最大值作为前后缀最大值的最小值必然增加，所以前一段递增；后期后缀最大值作为前后缀最大值的最小值必然减小，所以后一段递减，中间那段显然。

好了，关于无解我们先到这里。

对于 a 连续的一段，我们可以发现假如在左半边，这段的第一个位置必然取这一段的值，其他位置必然小于这一段的值，也不会在这一段中，否则则反其道而行之。

考虑对每一段的值从小到大排序。排序后，设值为 x，长度为 y，那么则需要从 p\in[1,x-1] 中选 y 个，再选一个 x，这似乎可以组合数，然而前面的数会影响 p 的取值，怎么办？其实我们排完序后，前面的必然会影响后面的取值，所以直接记录一下就好了，即第 i 段选的方案有 C_{x_i-1-\sum_{j=1}^{i-1}y_j}^{y_i-1}。当然，每段之间的元素可以互相乱传，所以还要乘上 (y_i-1)!。

最后，对于中间那一段，有两种方式，第一种 p_l=n-1,p_{r+1}=n，第二种 p_l=n,p_{r+1}=n-1。其他 i\in[l+1,r] 的数可以随便取，所以乘上 (r-l)! 就是最终答案了。

哈哈哈，终于做完了，如果没看懂可以搭配样例食用。

最后献上代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,maxn=1e6,P=998244353;
int T,n,a[N];
struct Node{
    int x,y;
    bool operator <(const Node &t)const{
        return x<t.x;
    }
}c[N];
int fac[N],inv[N];
int C(int n,int m){
    if(n<m||n<0||m<0)return 0;
    return 1LL*fac[n]*inv[m]%P*inv[n-m]%P;
}
int power(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=1LL*res*a%P;
        a=1LL*a*a%P;
        b>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    fac[0]=1;
    for(int i=1;i<=maxn;i++)fac[i]=1LL*fac[i-1]*i%P;
    inv[maxn]=power(fac[maxn],P-2);
    for(int i=maxn;i;i--)inv[i-1]=1LL*inv[i]*i%P;
    cin>>T;
    while(T--){
        bool flag=true;
        cin>>n;
        a[n]=0;
        int l=0,r=0;
        for(int i=1;i<n;i++){
            cin>>a[i];
            if(a[i]==n-1){
                if(!l)l=i;
                r=i;
            }
            if(a[i]==n)flag=false;
        }
        if(!l)flag=false;
        int m=0;
        for(int i=1;i<l;i++){
            if(a[i]>a[i+1])flag=false;
            if(a[i]!=a[i-1])c[++m].x=a[i];
            c[m].y++; 
        }
        for(int i=l;i<=r;i++)
            if(a[i]!=n-1)flag=false;
        for(int i=n-1;i>r;i--){
            if(a[i]<a[i+1])flag=false;
            if(a[i]!=a[i+1])c[++m].x=a[i];
            c[m].y++; 
        }
        sort(c+1,c+1+m);
        int cnt=0,ans=1;
        for(int i=1;i<=m;i++){
            if(c[i].x==c[i+1].x)flag=false;
            ans=1LL*ans*C(c[i].x-cnt-1,c[i].y-1)%P*fac[c[i].y-1]%P;
            cnt+=c[i].y;
            c[i]={0,0};
        }
        ans=2LL*ans*fac[r-l]%P;
        cout<<ans*flag<<'\n';
    }
    return 0;
}