fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5 + 50, mod = 998244353;
  4.  
  5. void work(vector<int>& a) {
  6.     for (int i = 1; i < a.size(); i++)
  7.     a[i] = (a[i] + a[i - 1]) % mod;
  8. }
  9.  
  10. int main() {
  11. 	ios::sync_with_stdio(false);
  12. 	cin.tie(nullptr);
  13.  
  14. 	int n;
  15. 	cin >> n;
  16. 	int a[n+1]{};
  17. 	for (int i = 1; i <= n; i++) {
  18. 	    cin >> a[i];
  19. 	}
  20.  
  21. 	if (n == 2) {
  22. 	    int ans = 0;
  23. 	    if (!~a[1] && !~a[2]) ans = 200;
  24. 	    else if (!~a[1] || !~a[2]) ans = 1;
  25. 	    else ans = (a[1] == a[2]);
  26. 	    cout << ans << endl;
  27. 	    return 0;
  28. 	}
  29.  
  30. 	vector<vector<int>> x, y;
  31.  
  32. 	vector<int> dp1(201, 0);
  33. 	if (a[1] == -1)
  34. 	    for (int i = 1; i <= 200; i++)
  35. 	        dp1[i] = 1;
  36. 	else dp1[a[1]] = 1;
  37. 	x.push_back(dp1);
  38.  
  39. 	work(dp1);
  40.  
  41. 	for (int i = 2; i <= n; i++) {
  42. 	    vector<int> ndp1(201);
  43.  
  44. 	    if (a[i] != -1) {
  45. 	        ndp1[a[i]] = dp1[a[i]];
  46. 	    }
  47. 	    else {
  48. 	        ndp1 = dp1;
  49. 	    }
  50. 	    x.push_back(ndp1);
  51. 	    dp1 = ndp1;
  52. 	    work(dp1);
  53. 	}
  54.  
  55. 	vector<int> dp2(201, 0);
  56. 	if (a[n] == -1)
  57. 	    for (int i = 1; i <= 200; i++)
  58. 	        dp2[i] = 1;
  59. 	else dp2[a[n]] = 1;
  60. 	y.push_back(dp2);
  61. 	work(dp2);
  62.  
  63. 	for (int i = n - 1; i >= 1; i--) {
  64. 	    vector<int> ndp2(201);
  65.  
  66. 	    if (~a[i]) {
  67. 	        ndp2[a[i]] = dp2[a[i]];
  68. 	    }
  69. 	    else {
  70. 	        ndp2 = dp2;
  71. 	    }
  72. 	    y.push_back(ndp2);
  73. 	    dp2 = ndp2;
  74. 	    work(dp2);
  75. 	}
  76. 	reverse(y.begin(), y.end());
  77.  
  78. 	int ans = 0;
  79. 	for (int i = 0; i < n; i++) {
  80. 	for (int j = 1; j <= 200; j++) {
  81. 	        int add = 1ll * x[i][j] * y[i][j] % mod;
  82. 	        ans = (ans + add) % mod;
  83. 	    }
  84. 	}
  85.  
  86. 	cout << ans << endl;
  87.  
  88. 	return 0;
  89. }
  90.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
3
1 -1 2
stdout
copy 
201
https://ideone.com/V2CtsT
language:
C++14 (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!