JacobianDet

Untitled

Oct 29th, 2018
282
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MOD 998244353
  3.  
  4. typedef long long ll;
  5.  
  6. int memo[100001][201][3];
  7. int arr[100001];
  8.  
  9. /* 0 = <
  10. 1 = =
  11. 2 = >
  12. */
  13.  
  14. int main(void)
  15. {
  16. std::ios_base::sync_with_stdio(false);
  17. std::cin.tie(NULL);
  18. std::cout.tie(NULL);
  19. ll n;
  20. std::cin>>n;
  21. for(int i=1;i<=n;i++)
  22. std::cin>>arr[i];
  23. if(arr[1] != -1)
  24. memo[1][arr[1]][1] = 1;
  25. else
  26. {
  27. for(int i=1;i<=200;i++)
  28. memo[1][i][1] = 1;
  29. }
  30. for(int i=1;i<=200;i++)
  31. {
  32. for(int j=0;j<3;j++)
  33. memo[1][i][j] = ((memo[1][i][j]%MOD) + (memo[1][i-1][j]%MOD))%MOD;
  34. }
  35. for(int i=2;i<=n;i++)
  36. {
  37. if(arr[i] != -1)
  38. {
  39. memo[i][arr[i]][0] = ((((memo[i-1][arr[i]-1][0]%MOD) + (memo[i-1][arr[i]-1][1]%MOD))%MOD) + (memo[i-1][arr[i]-1][2]%MOD))%MOD;
  40. memo[i][arr[i]][1] = ((((((memo[i-1][arr[i]][0]%MOD) - (memo[i-1][arr[i]-1][0]%MOD) + MOD)%MOD) + (((memo[i-1][arr[i]][1]%MOD) - (memo[i-1][arr[i]-1][1]%MOD) + MOD)%MOD))%MOD) + (((memo[i-1][arr[i]][2]%MOD) - (memo[i-1][arr[i]-1][2]%MOD) + MOD)%MOD))%MOD;
  41. if(i > 2)
  42. memo[i][arr[i]][2] = ((((memo[i-1][200][2]%MOD) - (memo[i-1][arr[i]][2]%MOD) + MOD)%MOD) + (((memo[i-1][200][1]%MOD) - (memo[i-1][arr[i]][1]%MOD) + MOD)%MOD))%MOD;
  43. }
  44. else
  45. {
  46. for(int j=1;j<=200;j++)
  47. {
  48. memo[i][j][0] = ((((memo[i-1][j-1][0]%MOD) + (memo[i-1][j-1][1]%MOD))%MOD) + (memo[i-1][j-1][2]%MOD))%MOD;
  49. memo[i][j][1] = ((((((memo[i-1][j][0]%MOD) - (memo[i-1][j-1][0]%MOD) + MOD)%MOD) + (((memo[i-1][j][1]%MOD) - (memo[i-1][j-1][1]%MOD) + MOD)%MOD))%MOD) + (((memo[i-1][j][2]%MOD) - (memo[i-1][j-1][2]%MOD) + MOD)%MOD))%MOD;
  50. if(i > 2)
  51. memo[i][j][2] = ((((memo[i-1][200][2]%MOD) - (memo[i-1][j][2]%MOD) + MOD)%MOD) + (((memo[i-1][200][1]%MOD) - (memo[i-1][j][1]%MOD) + MOD)%MOD))%MOD;
  52. }
  53. }
  54. for(int j=1;j<=200;j++)
  55. {
  56. for(int k=0;k<3;k++)
  57. memo[i][j][k] = ((memo[i][j][k]%MOD) + (memo[i][j-1][k]%MOD))%MOD;
  58. }
  59. }
  60. ll ax = (arr[n] != -1) ? (((((memo[n][arr[n]][2]%MOD) - (memo[n][arr[n]-1][2]%MOD) + MOD)%MOD) + (((memo[n][arr[n]][1]%MOD) - (memo[n][arr[n]-1][1]%MOD) + MOD)%MOD))%MOD) : (((memo[n][200][1]%MOD) + (memo[n][200][2]%MOD))%MOD);
  61. std::cout<<ax<<"\n";
  62. return 0;
  63. }
Add Comment
Please, Sign In to add comment