Untitled
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