fork download 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll long long           //                     https://m...content-available-to-author-only...a.nz/file/vJsRUbYY#B97-LFnpFJ0QTsdzI8fE-VdYS2NFByMNjIqYeE3NAa8
  4. #define ld long double
  5. #define el "\n"
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define __ROOT__ int main()
  8. #pragma GCC optimize("O2")
  9. //#pragma GCC optimize("unroll-loops")
  10. //#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
  11. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  12. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  13. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  14. #define fi first
  15. #define se second
  16. #define M 998244353
  17. #define MAXN 1000001
  18. #define INF (1ll<<30)  // https://c...content-available-to-author-only...s.com/group/rpEhKtCb3Q/contest/626452/problem/D
  19. #define BLOCK_SIZE 425
  20. #define MAX_NODE 1001001
  21. #define LOG 19
  22. #define ALPHA_SIZE 26
  23. #define BASE 256
  24. #define NAME "file"
  25. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  26. using namespace std;
  27. using namespace chrono ;
  28. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  29. const ll NMOD = 1;
  30. const int dx[] = {-1, 0, 1,0};
  31. const int dy[] = {0, 1, 0, -1};
  32. //**Variable**//
  33. ll n, ans = 0 ;
  34. ll arr[MAXN];
  35. ll cnt[MAXN] ;
  36. ll pref[MAXN] ;
  37. ll dp[MAXN][2] ;
  38. //**Struct**//
  39.  
  40. //**Function**//
  41. template<class X, class Y >
  42. bool minimize(X & x, const Y &y ) {
  43.     return x > y ? x = y, 1:0 ;
  44. }
  45. template<class X, class Y >
  46. bool maximize(X &x, const Y &y ) {
  47.     return x < y ? x = y, 1:0 ;
  48. }
  49. ll power(ll a, ll b ) {
  50.     ll res = 1;
  51.     while(b) {
  52.         if(b & 1 ) res = a * res % M ;
  53.         b >>=1 ;
  54.         a = a * a % M ;
  55.     }
  56.     return res ;
  57. }
  58. ll sub(ll a, ll b) {
  59.     return ((a - b ) % M + M) % M    ;
  60. }
  61. ll add(ll a, ll b ) {
  62.     return (a + b ) % M  ;
  63. }
  64. ll mul(ll a, ll b ) {
  65.     return a * b % M ;
  66. }
  67. void init() {
  68.     ans =0  ;
  69.     cin>>n;
  70.     FOR(i,1, n) cin >> arr[i], cnt[arr[i]] ++ ;
  71. }
  72.  
  73. void solve() { // goi dp[i][0./1] laf so cahc chon tap tu 0 -> i-1 co du hay thieu 1 so
  74.     dp[0][0] = 1 ;
  75.     FOR(i, 1, n + 1 ) dp[i][0] = ( mul( sub(power(2, cnt[i-1]), 1 ), dp[i-1][0] ) ) ;
  76.     FOR(i, 1,  n + 1 ) {
  77.         dp[i][1] = mul(dp[i-1][1], sub(power(2, cnt[i -1 ] ), 1 )) ;
  78.         dp[i][1] = add(dp[i][1], dp[i-1][0 ]) ;
  79.     }
  80.     pref[0] = cnt[0] ;
  81.     FOR(i, 1, n + 1  ) pref[i] = pref[i-1] + cnt[i] ;
  82.     FOR(i, 0, n + 1 )  ans = add(ans, mul(mul(dp[i][1], i), power(2, n - pref[i]))  ) ;
  83.     cout << sub(ans , 1 )  << el  ;
  84. }
  85. void reset() {
  86.     FOR(i, 0, n + 1) dp[i][0] = dp[i][1] = cnt[i] = pref[i] = 0 ;
  87. }
  88. __ROOT__ {
  89.     // freopen(NAME".inp" , "r" , stdin);
  90.     // freopen(NAME".out" , "w", stdout) ;
  91.     fast;
  92.     int t = 1;
  93.     cin >> t ;
  94.     while(t--) {
  95.         init();
  96.         solve();
  97.         reset() ;
  98.     }
  99.     return (0&0);
  100. }
  101.  
  102.  
  103.  
  104.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Bố thí
stdout 
Standard output is empty
https://ideone.com/c2i0oa
language:
C++14 (gcc 8.3)
created:
9 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!