题意：

对数组中的任何一个数，要求存在一个相邻数大于等于它。数组中的一些数未确定（记为-1），求填数方案数，对 998244353 取模。

n <= 2e5, 1 <= a[i] <= 200

思路：

前缀和优化的dp

\(f(i,j,1)\) 表示填完了 \(a[1,i]\) ，最后一位 \(a_i=j\) ，且 \(a_{i-1} \ge a_i\) ； \(f(i,j,0)\) 表示 \(a_{i-1} < a_i\) 。

得到一个 \(O(na^2)\) 做法，会超时：

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= 200; j++) //枚举第i位
    {
        if(a[i] > 0 && a[i] != j) continue;

        for(int k = 1; k <= 200; k++) //上一位即第i-1位
        {
            if(a[i-1] > 0 && a[i-1] != k) continue;

            if(j < k) f[i][j][1] += f[i-1][k][1];
            if(j == k) f[i][j][1] += f[i-1][k][1] + f[i-1][k][0];
            if(j > k) f[i][j][0] += f[i-1][k][1] + f[i-1][k][0];
        }
    }

观察发现，\(f(i,j,1)=f(i-1,j,0) + \sum_{k\ge j} f(i-1,k,1)\) ，\(f(i,j,1)= \sum_{k< j} f(i-1,k,1)+\sum_{k< j} f(i-1,k,0)\) 。用前缀和优化到 \(O(na)\)。

注意第 \(i-1\) 位已经有数 \(a_{i-1}\) 说明第 \(i-1\) 层只在 \(a_{i-1}\) 处有值，其他全是0。笑死，根本不用管。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5, p = 998244353;
int n, a[N]; ll f[N][203][2];
signed main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    if(a[1] > 0) f[1][a[1]][0] = 1; //初始化, 不合法的方案置零
    else for(int i = 1; i <= 200; i++) f[1][i][0] = 1;

    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j <= 200; j++) //上一层的前缀和
            f[i-1][j][1] += f[i-1][j-1][1],
            f[i-1][j][0] += f[i-1][j-1][0];

        for(int j = 1; j <= 200; j++) //第i位
        {
            if(a[i] > 0 && a[i] != j) continue;

            f[i][j][1] += f[i-1][j][0] - f[i-1][j-1][0];
            f[i][j][1] += f[i-1][200][1] - f[i-1][j-1][1];
            f[i][j][0] += f[i-1][j-1][0] - f[i-1][0][0];
            f[i][j][0] += f[i-1][j-1][1] - f[i-1][0][1];

            f[i][j][1] %= p, f[i][j][0] %= p;
        }
    }

    ll ans = 0;
    for(int j = 1; j <= 200; j++) ans += f[n][j][1];
    cout << (ans + p) % p;

    return 0;
}