JacobianDet

Untitled

Oct 29th, 2018
304
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MOD 998244353
  3.  
  4. /* 0 = <
  5. 1 = =
  6. 2 = >
  7. */
  8.  
  9. typedef long long ll;
  10.  
  11. int arr[100001];
  12. int memo[100001][201][4];
  13.  
  14. int n;
  15.  
  16. int jacobian(int i, int val, int sg)
  17. {
  18. if(i == n+1)
  19. return 1;
  20. if(memo[i][val][sg] != -1)
  21. return memo[i][val][sg];
  22. int ans = 0;
  23. if(arr[i] != -1)
  24. {
  25. if(i == 1)
  26. ans = ((jacobian(i+1, arr[i], 0)%MOD) + (jacobian(i+1, arr[i], 1)%MOD))%MOD;
  27. else if((i > 1) && (i < n))
  28. {
  29. if(((val < arr[i]) && ((sg == 1) || (sg == 2))) || ((val == arr[i]) && ((sg == 0) || (sg == 2))) || ((val > arr[i]) && ((sg == 0) || (sg == 1))))
  30. ans = 0;
  31. else
  32. {
  33. if(!sg)
  34. ans = ((jacobian(i+1, arr[i], 0)%MOD) + (jacobian(i+1, arr[i], 1)%MOD))%MOD;
  35. else if(sg == 1)
  36. ans = ((((jacobian(i+1, arr[i], 0)%MOD) + (jacobian(i+1, arr[i], 1)%MOD))%MOD) + (jacobian(i+1, arr[i], 2)%MOD))%MOD;
  37. 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;
  38. }
  39. }
  40. else
  41. {
  42. if((((val < arr[i]) && ((sg == 1) || (sg == 2))) || ((val == arr[i]) && ((sg == 0) || (sg == 2))) || ((val > arr[i]) && ((sg == 0) || (sg == 1)))) || (!sg))
  43. ans = 0;
  44. else ans = jacobian(i+1, arr[i], 3)%MOD;
  45. }
  46. }
  47. else
  48. {
  49. for(int j=1;j<=200;j++)
  50. {
  51. if(i == 1)
  52. ans = ((ans%MOD) + (((jacobian(i+1, j, 0)%MOD) + (jacobian(i+1, j, 1)%MOD))%MOD))%MOD;
  53. else if((i > 1) && (i < n))
  54. {
  55. if(((val < j) && ((sg == 1) || (sg == 2))) || ((val == j) && ((sg == 0) || (sg == 2))) || ((val > j) && ((sg == 0) || (sg == 1))))
  56. continue;
  57. else
  58. {
  59. if(!sg)
  60. ans = ((ans%MOD) + (((jacobian(i+1, j, 0)%MOD) + (jacobian(i+1, j, 1)%MOD))%MOD))%MOD;
  61. else if(sg == 1)
  62. ans = ((ans%MOD) + (((((jacobian(i+1, j, 0)%MOD) + (jacobian(i+1, j, 1)%MOD))%MOD) + (jacobian(i+1, j, 2)%MOD))%MOD))%MOD;
  63. 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;
  64. }
  65. }
  66. else
  67. {
  68. if((((val < j) && ((sg == 1) || (sg == 2))) || ((val == j) && ((sg == 0) || (sg == 2))) || ((val > j) && ((sg == 0) || (sg == 1)))) || (!sg))
  69. continue;
  70. else ans = ((ans%MOD) + (jacobian(i+1, j, 3)%MOD))%MOD;
  71. }
  72. }
  73. }
  74. memo[i][val][sg] = ans;
  75. return ans;
  76. }
  77.  
  78. int main(void)
  79. {
  80. std::ios_base::sync_with_stdio(false);
  81. std::cin.tie(NULL);
  82. std::cout.tie(NULL);
  83. memset(memo, -1, sizeof(memo));
  84. std::cin>>n;
  85. for(int i=1;i<=n;i++)
  86. std::cin>>arr[i];
  87. int ans = jacobian(1, 0, 3)%MOD;
  88. std::cout<<ans<<"\n";
  89. return 0;
  90. }
Add Comment
Please, Sign In to add comment