Untitled

 avatar
unknown
plain_text
2 months ago
1.7 kB
7
Indexable
// OMI_14
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define faster                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
using namespace std;
ll dp[200000 + 1][2];
ll a[200000 + 1];
const ll mod = 998244353;
// unordered_map<ll, ll> mp;
// mp.reserve(1024);
// mp.max_load_factor(1)
ll func(int inx, int flag)
{
    if (inx == 0)
    {
        if (flag && !a[inx])
            return 1;
        else if (flag && a[inx])
            return 0;
        else if (!flag)
            return 1;
    }
    if (dp[inx][flag] != -1)
        return dp[inx][flag];
    ll x = 0;
    if (flag)
    {
        if (inx - 2 >= 1 && a[inx - 2] + 1 == a[inx])
            x = (x + func(inx - 1, 0)) % mod;
        if (inx - 1 >= 1 && a[inx] == a[inx - 1])
            x = (x + func(inx - 1, 1)) % mod;
    }
    else
    {
        x = (x + func(inx - 1, 1)) % mod;
    }
    return dp[inx][flag] = x % mod;
}
int main()
{
    faster;
    // freopen("input.txt","r",stdin);
    // freopen("output1.txt","w",stdout);

    int t;
    cin >> t;
    while (t--)
    {

        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int x;
            cin >> x;
            a[i] = x;
        }
        for (int i = 0; i < n; i++)
        {
            dp[i][1] = -1;
            dp[i][0] = -1;
        }
        ll y = func(n - 1, 1) % mod;
        for (int i = 0; i < n; i++)
        {
            dp[i][1] = -1;
            dp[i][0] = -1;
        }
        ll z = func(n - 1, 0) % mod;
        cout << y + z << "\n";
    }
    //  fclose(stdin);
    //  fclose(stdout);

    return 0;
}
Editor is loading...
Leave a Comment