专栏文章

CF2154F2

xxujindong_
CF2154F2题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minabbfv
此快照首次捕获于
2025/12/01 23:08
3 个月前
此快照最后确认于
2025/12/01 23:08
3 个月前
查看原文
考虑合法排列的形态。有序排列是例外。对于其他排列，会有一段红色的前缀和蓝色的后缀不动，中间的一段红色的每个数都必须往后动，蓝色的必须往前动。因此中间这一段都满足 pi≠ip_i\ne i，且红色的满足 pi<ip_i<i，蓝色的满足 pi>ip_i>i。此时分成两种情况讨论：
若可能形成有序排列，即不存在 pi≠−1∧pi≠ip_i\ne-1\wedge p_i\ne i。假设实际排列不是有序排列，枚举 pi≠ip_i\ne i 在哪个段里，其他段确定，这一段内元素自由染红或蓝，排除有序排列的情况，为 2len−len−12^{len}-len-1。每一段加起来，最后加上有序排列的 11。
否则， 通过 pi≠−1∧pi≠ip_i\ne-1\wedge p_i\ne i 的元素可以唯一确定不为 −1-1 的位置的颜色。设红蓝的分界点为 xx，红色为 [1,x)[1,x)，蓝色为 [x,n][x,n]。对不有序的排列都可唯一确定分界点为第一个 pi>ip_i>i 的数，所以可以枚举每个 xx。
枚举 xx 后，枚举每个 −1-1 的连续段 (l,r)(l,r) 将方案数相乘，我们可以计算出这一段里红蓝的个数。若 l,rl,r 颜色相同，方案数是 Cr−l−1pr−pl−1C_{r-l-1}^{p_r-p_l-1}。否则不妨设 ll 是红色，rr 是蓝色。[1,l][1,l] 的红色数为 ala_l，[1,r)[1,r) 的红色数为 r−(ar−x+1)r-(a_r-x+1)，(l,r)(l,r) 的红色数为 r−ar+x−al−1r-a_r+x-a_l-1，方案数 Cr−l−1r−ar+x−al−1C_{r-l-1}^{r-a_r+x-a_l-1}。发现对于每一段，只有 r−lr-l 个 xx 可能合法，直接枚举这些 xx 就是 O(n)O(n) 的。
CPP
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int t,n,a[1000005],p2[1000005],fac[1000005],vac[1000005],ans[1000005];
bool type[1000005];
int C(int n,int m){
  return n<0||m<0||n<m?0:1ll*fac[n]*vac[m]%mod*vac[n-m]%mod;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),p2[0]=fac[0]=vac[0]=vac[1]=1;
  for(int i=2;i<=1000000;i++)vac[i]=1ll*vac[mod%i]*(mod-mod/i)%mod;
  for(int i=1;i<=1000000;i++)p2[i]=2*p2[i-1]%mod,fac[i]=1ll*fac[i-1]*i%mod,vac[i]=1ll*vac[i]*vac[i-1]%mod;
  cin>>t;
  while(t--){
    cin>>n,a[n+1]=n+1;
    for(int i=1;i<=n;i++)cin>>a[i];
    bool flag=1;
    for(int i=1;i<=n;i++)if(a[i]!=-1&&a[i]!=i)flag=0;
    if(flag){
      int ans=1;
      for(int i=1,pre=0;i<=n+1;i++)if(a[i]!=-1)ans=(ans+p2[i-pre-1]-(i-pre))%mod,pre=i;
      cout<<ans<<'\n';
      continue;
    }
    int l=2,r=n,prod=1;
    for(int i=1,pre=0;i<=n+1;i++){
      if(a[i]==-1)continue;
      if(a[i]<i)flag=1,type[i]=0;
      else if(a[i]>i)flag=1,type[i]=1;
      else type[i]=flag;
      if(type[i]==type[pre])prod=1ll*prod*C(i-pre-1,a[i]-a[pre]-1)%mod;
      else l=max(l,a[i]-i+a[pre]+1),r=min(r,a[i]-pre+a[pre]);
      pre=i;
    }
    if(!prod||l>r){
      cout<<0<<'\n';
      continue;
    }
    for(int i=l;i<=r;i++)ans[i]=1;
    for(int i=1,pre=0;i<=n+1;i++){
      if(a[i]==-1)continue;
      if(type[i]!=type[pre])for(int j=l;j<=r;j++)ans[j]=1ll*ans[j]*C(i-pre-1,i-a[i]+j-a[pre]-1)%mod;
      pre=i;
    }
    int sum=0;
    for(int i=l;i<=r;i++)sum=(sum+ans[i])%mod;
    cout<<1ll*sum*prod%mod<<'\n';
  }
  return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...