题解：CF2249B Permutation Cuts

fish_love_cat · 2026-08-09 21:10:50 · 题解

首先肯定有位置是 n-1，不会有位置是 n。

然后整个数列一定是一个前缀不降后缀不升的形式，并且断点处的元素是已经确定的。

注意到放置数字必须满足往中心方向的所有被钦定的数字都不能低于当前位置的值。

从大到小考虑放置的数字，容易发现允许放置的区间从中间开始向两侧扩展，每步操作我们都可以任意选择放置，显然不影响合法性。

那这个就很好了，直接模拟计数就做完了，可以做到线性。

有一百万个无解的 corner case，请仔细实现。赛时严肃被罚飞 /ll

int a[1000005];
inline void solve(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    cin>>a[i];
    vector<pair<int,int>>v1,v2;
    bool flg=0;
    int L;
    for(int i=1;i<n;i++){
        if(a[i]==n-1){
            L=i;
            flg=1;
            for(int j=1;j<i;j++){
                if(!v1.empty()&&v1[v1.size()-1].first!=a[j]||v1.empty())
                v1.push_back({a[j],j});
                if(a[j]>a[j+1]){
                    cout<<"0\n";
                    return;
                }
            }
            for(int j=n-1;j>=i;j--){
                if(a[j]!=n-1)
                if(!v2.empty()&&v2[v2.size()-1].first!=a[j]||v2.empty())
                v2.push_back({a[j],j+1});
                if(j!=n-1&&a[j]<a[j+1]){
                    cout<<"0\n";
                    return;
                }
            }
            break;
        }
    }
    int R;
    for(int i=n-1;i;i--)
    if(a[i]==n-1){R=i+1;break;}
    if(!flg){
        cout<<"0\n";
        return;
    }
    map<int,bool>mp;
    for(pair<int,int>i:v1)mp[i.first]=1;
    for(pair<int,int>i:v2)
    if(mp[i.first]){
        cout<<"0\n";
        return;
    }else mp[i.first]=1;
    reverse(v1.begin(),v1.end());
    reverse(v2.begin(),v2.end());
    int l=0,r=0;
    int ans=2;
    for(int i=n-2;i;i--){
        if(mp[i])continue;
        while(l<v1.size()&&v1[l].first>i)L=v1[l].second,l++;
        while(r<v2.size()&&v2[r].first>i)R=v2[r].second,r++;
        if(R-L+1-(n-i)<=0){
            cout<<"0\n";
            return;
        }
        ans=ans*(R-L+1-(n-i))%mod;
    }
    cout<<ans<<'\n';
}
signed main(){
    int t=1;
    t=read();
    while(t--)solve();
    return 0;
}
// 事到如今 懒得想什么明天
// 抬眼只剩下没有转晴迹象的阴霾
// 招朋引伴 尽兴后匆忙四散
// 道别也不忍将偶像乏味感言打断
// 百无聊赖 将折成的纸飞机的传单展开
// 为奔波生计的油墨外 有潦草勾画的未来

// 从我又小又拥挤的房间
// 从我堆满了贪念的床边
// 飞向总有容身处的世界
// 却碎裂 却碎裂
// 在那四处是虫鸣的夏夜
// 在那潮湿又安静的街边
// 笨拙打着拍子的陌生人
// 都不见