ARC 187 C

首先扔出一个结论，如果 \(Q\) 中没有 \(-1\)，那么答案是 \(2^k\)，其中 \(k=\sum_{i=2}^n [Q_i=\max(P_{1\sim i})]\)。考虑证明。

设 \(Q_i=\max(P_{1\sim i})\) 的位置（包含 \(i=1\)）是 \(a_1\sim a_{k+1}\)。那么设 \(f_i\) 为 \(1\sim a_i\) 的答案，显然 \(f_1=1\)。考虑 \(Q_{a_i}\) 放哪。我们发现可以插在前面一个前缀最大值 \(a_j\) 的正后方，而 \(a_j+1\sim a_i\) 是啥都固定了，并且 \(1\sim a_j\) 是 \(f_j\)。那么得出 \(f_i=\sum_{j=1}^{i-1}f_j\)，则 \(f_1=1,f_2=1,f_3=1+1=2,f_4=1+1+2=4,\cdots, f_{k+1}=2^k\)。

因此设 \(f_{i,j}\) 为前 \(i\) 位，现在 \(\max\) 是 \(j\) 的答案即可。为了方便，设 \(Q_0=0\)，最后答案是 \(\frac{f_{n,n}}{2}\)。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 5e3+3;
const ll mod = 998244353;
const ll i2 = (mod+1)/2;

int n,m,a[N],vis[N],t[N];
ll f[N],s[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for (int i=1; i<=n; i++){
		cin>>a[i];
		if (a[i]!=-1) vis[a[i]]=1;
	}
	for (int i=1; i<=n; i++){
		t[i]=t[i-1]+(vis[i]==0);
	}
	f[0]=1;
	for (int i=1,c=0; i<=n; i++){
		if (a[i]!=-1){
			for (int j=1; j<=a[i]; j++){
				f[j]=(f[j]+f[j-1])%mod;
				f[j-1]=0;
			}
			f[a[i]]=(f[a[i]]+f[a[i]])%mod;
		}
		else{
			s[0]=f[0];
			for (int j=1; j<=n; j++){
				s[j]=(f[j]+s[j-1])%mod;
			}
			f[0]=0;
			for (int j=1; j<=n; j++){
				f[j]=(f[j]*(t[j]-c)%mod+s[j-1]*2*(!vis[j]))%mod;
			}
			c++;
		}
		if (i!=n) f[n]=0;
	}
	cout<<f[n]*i2%mod<<"\n";
	return 0;
}