题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N = 10010, M = 210;
const LL mod = 998244353;

int a[N];
LL f[N][M][3], s1[M], s2[M];
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    for (int i = (a[1] ? a[1] : 1); i <= (a[1] ? a[1] : 200); i ++)
        for (int j = (a[2] ? a[2] : 1); j <= (a[2] ? a[2] : 200); j ++)
        {
            if (i == j) f[2][j][1] ++;
            else if (i < j) f[2][j][2] ++;
        }

    for (int i = 1; i <= 200; i ++)
    {
        s1[i] = s1[i - 1] + f[2][i][0] + f[2][i][1];
        s2[i] = s2[i - 1] + f[2][i][0] + f[2][i][1] + f[2][i][2];
    }

    for (int i = 3; i <= n; i ++)
    {
        for (int j = (a[i] ? a[i] : 1); j <= (a[i] ? a[i] : 200); j ++)
        {
            f[i][j][0] = (s1[200] - s1[j])  % mod;
            f[i][j][1] = (f[i - 1][j][0] + f[i - 1][j][1] + f[i - 1][j][2]) % mod;
            f[i][j][2] = s2[j - 1] % mod;
        }
        for (int j = 1; j <= 200; j ++)
        {
            s1[j] = s1[j - 1] + f[i][j][0] + f[i][j][1];
            s2[j] = s2[j - 1] + f[i][j][0] + f[i][j][1] + f[i][j][2];
        }
    }

    LL res = 0;
    for (int i = (a[n] ? a[n] : 1); i <= (a[n] ? a[n] : 200); i ++)
        res = (res + f[n][i][0] + f[n][i][1]) % mod;

    cout << (res + mod) % mod;

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla