Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MOD 998244353
- /* 0 = <
- 1 = =
- 2 = >
- */
- typedef long long ll;
- int arr[100001];
- int memo[100001][201][4];
- int n;
- int jacobian(int i, int val, int sg)
- {
- if(i == n+1)
- return 1;
- if(memo[i][val][sg] != -1)
- return memo[i][val][sg];
- int ans = 0;
- if(arr[i] != -1)
- {
- if(i == 1)
- ans = ((jacobian(i+1, arr[i], 0)%MOD) + (jacobian(i+1, arr[i], 1)%MOD))%MOD;
- else if((i > 1) && (i < n))
- {
- if(((val < arr[i]) && ((sg == 1) || (sg == 2))) || ((val == arr[i]) && ((sg == 0) || (sg == 2))) || ((val > arr[i]) && ((sg == 0) || (sg == 1))))
- ans = 0;
- else
- {
- if(!sg)
- ans = ((jacobian(i+1, arr[i], 0)%MOD) + (jacobian(i+1, arr[i], 1)%MOD))%MOD;
- else if(sg == 1)
- ans = ((((jacobian(i+1, arr[i], 0)%MOD) + (jacobian(i+1, arr[i], 1)%MOD))%MOD) + (jacobian(i+1, arr[i], 2)%MOD))%MOD;
- else ans = ((jacobian(i+1, arr[i], 0)%MOD) + (((jacobian(i+1, arr[i], 1)%MOD) + (jacobian(i+1, arr[i], 2)%MOD))%MOD))%MOD;
- }
- }
- else
- {
- if((((val < arr[i]) && ((sg == 1) || (sg == 2))) || ((val == arr[i]) && ((sg == 0) || (sg == 2))) || ((val > arr[i]) && ((sg == 0) || (sg == 1)))) || (!sg))
- ans = 0;
- else ans = jacobian(i+1, arr[i], 3)%MOD;
- }
- }
- else
- {
- for(int j=1;j<=200;j++)
- {
- if(i == 1)
- ans = ((ans%MOD) + (((jacobian(i+1, j, 0)%MOD) + (jacobian(i+1, j, 1)%MOD))%MOD))%MOD;
- else if((i > 1) && (i < n))
- {
- if(((val < j) && ((sg == 1) || (sg == 2))) || ((val == j) && ((sg == 0) || (sg == 2))) || ((val > j) && ((sg == 0) || (sg == 1))))
- continue;
- else
- {
- if(!sg)
- ans = ((ans%MOD) + (((jacobian(i+1, j, 0)%MOD) + (jacobian(i+1, j, 1)%MOD))%MOD))%MOD;
- else if(sg == 1)
- ans = ((ans%MOD) + (((((jacobian(i+1, j, 0)%MOD) + (jacobian(i+1, j, 1)%MOD))%MOD) + (jacobian(i+1, j, 2)%MOD))%MOD))%MOD;
- else ans = ((ans%MOD) + ((jacobian(i+1, j, 0)%MOD) + (((jacobian(i+1, j, 1)%MOD) + (jacobian(i+1, j, 2)%MOD))%MOD))%MOD)%MOD;
- }
- }
- else
- {
- if((((val < j) && ((sg == 1) || (sg == 2))) || ((val == j) && ((sg == 0) || (sg == 2))) || ((val > j) && ((sg == 0) || (sg == 1)))) || (!sg))
- continue;
- else ans = ((ans%MOD) + (jacobian(i+1, j, 3)%MOD))%MOD;
- }
- }
- }
- memo[i][val][sg] = ans;
- return ans;
- }
- int main(void)
- {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(NULL);
- std::cout.tie(NULL);
- memset(memo, -1, sizeof(memo));
- std::cin>>n;
- for(int i=1;i<=n;i++)
- std::cin>>arr[i];
- int ans = jacobian(1, 0, 3)%MOD;
- std::cout<<ans<<"\n";
- return 0;
- }
Add Comment
Please, Sign In to add comment