fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. #include <vector>
  4. #include <stack>
  5. #include <queue>
  6. #include <deque>
  7. #include <utility>
  8. #include <set>
  9. #include <map>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include<algorithm>
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. #include <ext/pb_ds/tree_policy.hpp>
  15. #define IOF ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  16. #define ll long long
  17. #define ld long double
  18. #define cy cout << "YES" << '\n';
  19. #define cn cout << "NO" << '\n';
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23. template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  24. template<typename T>
  25. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  26.  
  27. int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
  28. int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
  29. int knightX[] = {-2, -2, 2, 2, 1, 1 , -1, -1};
  30. int knighty[] = {-1, 1, -1, 1, -2, 2, -2, 2};
  31. char di[] = {'D', 'L', 'U', 'R'};
  32. const int N =3e5+5;
  33. const ll MOD = 998244353;
  34. void FOI(){
  35.     freopen("input.txt", "r" , stdin);
  36.     freopen("output.txt", "w" , stdout);
  37. }
  38.  
  39. //check ur idea
  40.  
  41. ll fast_power(ll x, ll p, ll m) {
  42.     if (p == 0) return 1;
  43.     if (p % 2 != 0)
  44.         return (x * fast_power(x, p - 1, m)) % m;
  45.     ll t = fast_power(x, p / 2, m);
  46.     return (t * t) % m;
  47. }
  48. ll modInv(ll a, ll m) {
  49.     return fast_power(a, m - 2, m);
  50. }
  51.  
  52. void solve(){
  53. int n ;cin >> n;
  54. ll arr[n];
  55. for(int i = 0 ; i < n ; i++)cin >> arr[i];
  56. ll cnt1 = 0 , cnt2 = 0 , tmp = 0;
  57. ll ans = 0;
  58. for (int i = 0; i < n; i++){
  59.     if(arr[i] == 1){
  60.     cnt1++;
  61.     tmp = (tmp%MOD + modInv(fast_power(2 , cnt2 , MOD), MOD)%MOD) % MOD;
  62.     }
  63.     else if(arr[i] == 2){
  64.     cnt2++;
  65.     } 
  66.     else{
  67.     ans = (ans%MOD +((fast_power(2 , cnt2 , MOD) * tmp) % MOD - cnt1 + MOD) % MOD) % MOD;
  68.     }
  69. }
  70.  
  71.     cout << ans << "\n";
  72.  
  73. }
  74.  
  75.  
  76.  
  77.  
  78. int main() {
  79.  
  80.  
  81.     IOF
  82.     ll t = 1;
  83.     cin >> t;
  84.     while (t--) {
  85.     solve() ;
  86.  
  87.     }
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5794
https://ideone.com/TjU6wO
language:
C++ (gcc 8.3)
created:
4 days 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!