CF2154F2

· · 题解

考虑合法排列的形态。有序排列是例外。对于其他排列，会有一段红色的前缀和蓝色的后缀不动，中间的一段红色的每个数都必须往后动，蓝色的必须往前动。因此中间这一段都满足 p_i\ne i，且红色的满足 p_i<i，蓝色的满足 p_i>i。此时分成两种情况讨论：

若可能形成有序排列，即不存在 p_i\ne-1\wedge p_i\ne i。假设实际排列不是有序排列，枚举 p_i\ne i 在哪个段里，其他段确定，这一段内元素自由染红或蓝，排除有序排列的情况，为 2^{len}-len-1。每一段加起来，最后加上有序排列的 1。

否则， 通过 p_i\ne-1\wedge p_i\ne i 的元素可以唯一确定不为 -1 的位置的颜色。设红蓝的分界点为 x，红色为 [1,x)，蓝色为 [x,n]。对不有序的排列都可唯一确定分界点为第一个 p_i>i 的数，所以可以枚举每个 x。

枚举 x 后，枚举每个 -1 的连续段 (l,r) 将方案数相乘，我们可以计算出这一段里红蓝的个数。若 l,r 颜色相同，方案数是 C_{r-l-1}^{p_r-p_l-1}。否则不妨设 l 是红色，r 是蓝色。[1,l] 的红色数为 a_l，[1,r) 的红色数为 r-(a_r-x+1)，(l,r) 的红色数为 r-a_r+x-a_l-1，方案数 C_{r-l-1}^{r-a_r+x-a_l-1}。发现对于每一段，只有 r-l 个 x 可能合法，直接枚举这些 x 就是 O(n) 的。

#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;
}