题解：AT_arc187_c [ARC187C] 1 Loop Bubble Sort

设 c_i 表示 [1,i-1] 中比 a_i 大的数量，那么有经典结论：一次冒泡排序相当于全部 -1 再整体左移一位，最后所有 c 对 0 取 max。所以容易发现，对于一个固定的排列 p，答案就是 2^{x-1}，x 表示 p 对应的 c 序列中 0 的数量，也就是前缀最大值的数量。

于是可以直接进行 dp 了。设 f_{i,j} 表示目前填完了值域 [i,n]，当前的前缀最大值填到了 j。转移可以分成放在 j 前面 / 后面两种情况考虑。

如果这个数已经出现，直接放到对应位置上。如果没有出现，放在前面就是枚举一个 -1，把 j 转移到这个位置上；放在后面的话，所有 -1 本质相同，可以直接乘上一个 -1 个数的系数。发现所有系数都与 i,j 相关，不需要额外记录维度了。放前面的转移可以用前缀和优化，因此时间复杂度为 \mathcal O(n^2)。

注意特判无解的情况。

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=5009,Mod=998244353;
ll n,a[N],pos[N],dp[N][N],suf[N],sq[N],sum[N],b[N],c[N];
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read();
    rep(i,1,n)a[i]=read();
    if(n<=10){
        rep(i,1,n)b[i]=i;
        ll ans=0;
        do{
            rep(i,1,n)c[i]=b[i];
            rep(i,1,n-1){
                if(c[i]>c[i+1])swap(c[i],c[i+1]);
            }
            ll fl=1;
            rep(i,1,n){
                if(~a[i]&&c[i]!=a[i]){
                    fl=0;
                    break;
                }
            }
            if(fl)ans++;
        }while(next_permutation(b+1,b+n+1));
        write(ans%Mod);
        return 0;
    }
    rep(i,1,n){
        if(~a[i])pos[a[i]]=i;
    }
    if(pos[n]&&pos[n]!=n)return puts("0"),0;
    if(~a[n]&&a[n]!=n)return puts("0"),0;
    a[n]=n,pos[n]=n;
    per(i,n,1){
        suf[i]=suf[i+1];
        if(!~a[i])suf[i]++;
    }
    dp[n][n]=1;
    per(i,n,1){
        sq[i]=sq[i+1];
        if(!pos[i])sq[i]++;
    }
    per(i,n,1){
        per(j,n,1)sum[j]=(sum[j]+sum[j+1])%Mod;
        rep(j,1,n){
            if(!~a[j])dp[i][j]=(dp[i][j]+sum[j])%Mod;
        }
        if(i==1)break;
        memset(sum,0,sizeof(sum));
        rep(j,1,n){
            if(!dp[i][j])continue;
            ll cnt=suf[j]-sq[i];
            if(cnt<0)continue;
            if(pos[i-1]){
                if(pos[i-1]==j)continue;
                if(pos[i-1]>j)dp[i-1][j]=(dp[i-1][j]+dp[i][j])%Mod;
                else dp[i-1][pos[i-1]]=(dp[i-1][pos[i-1]]+dp[i][j]*2)%Mod;
            }
            else {
                dp[i-1][j]=(dp[i-1][j]+dp[i][j]*cnt)%Mod;
                sum[j-1]=(sum[j-1]+dp[i][j]*2)%Mod;
            }
        }
    }
    write(dp[1][1]%Mod),putchar('\n');
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}