fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int mod=998244353;
  4. long long findPower(long long x,int y){
  5. x=x%mod;
  6. long long res=1;
  7. while(y>0){
  8.     if(y&1)
  9.         res=(res*x)%mod;
  10.     y=y>>1;
  11.     x=(x*x)%mod;
  12. }
  13. return res;
  14. }
  15. int main(){
  16. int t,i,a;
  17. cin>>t;
  18. while(t--){
  19.     int n;
  20.     cin>>n;
  21.     int arr[n+1];
  22.     for(i=0;i<n;i++)
  23.         cin>>arr[i];
  24.     sort(arr,arr+n);
  25.     long long ans=0;
  26.     if(arr[0]>1){
  27.         ans=findPower(2,n);
  28.         cout<<ans<<endl;
  29.         continue;
  30.     }
  31.     else if(arr[0]==arr[n-1]){
  32.         ans=(((findPower(2,n)-1)*2)%mod+1)%mod;
  33.         cout<<ans<<endl;
  34.         continue;
  35.     }
  36.     vector<pair<int,int> > v;
  37.     int current=1;
  38.     int size=0;
  39.     for(i=0;i<n;a++){
  40.         size=0;
  41.         while(i<n&&arr[i]==current){
  42.             size++;
  43.             i++;
  44.         }
  45.         v.push_back(make_pair(current,size));
  46.         current=arr[i];
  47.     }
  48.     int remSize=n,ending=0;
  49.     bool flag=true;
  50.     for(i=1;i<v.size();i++){
  51.         if((v[i].first-v[i-1].first)!=1){
  52.             flag=false;
  53.             break;
  54.         }
  55.     }
  56.     if(!flag)
  57.         ending=i-1;
  58.     else
  59.         ending=v.size()-1;
  60.     v.push_back(make_pair(0,0));
  61.     ans=findPower(2,n-v[0].second);
  62.     long long oldComer=1,newComer,here,finaly;
  63.     for(i=0;i<ending;i++){
  64.         remSize=remSize-v[i].second;
  65.         newComer=(((findPower(2,v[i].second)-1+mod)%mod)*(oldComer%mod))%mod;
  66.         here=(newComer*findPower(2,(remSize-v[i+1].second)))%mod;
  67.         ans=(ans+(here*(v[i].first+1))%mod)%mod;
  68.         oldComer=newComer;
  69.         finaly=remSize-v[i+1].second;
  70.     }
  71.     if(!flag){
  72.          newComer=(((findPower(2,v[i].second)-1+mod)%mod)*(oldComer%mod))%mod;
  73.          here=(newComer*findPower(2,finaly))%mod;
  74.          ans=(ans+(here*(v[i].first+1))%mod)%mod;
  75.     }
  76.     else{
  77.         remSize=remSize-v[i].second;
  78.         newComer=(((findPower(2,v[i].second)-1+mod)%mod)*(oldComer%mod))%mod;
  79.         here=(newComer*findPower(2,(remSize-v[i+1].second)))%mod;
  80.         ans=(ans+(here*(v[i].first+1))%mod)%mod;
  81.         oldComer=newComer;
  82.     }
  83.     cout<<ans<<endl;
  84. }
  85. }
  86.  
Success #stdin #stdout 0s 4116KB
comments (?)
stdin
copy 
2
2
1 1
3
1 2 1
stdout
copy 
7
17
https://ideone.com/IFMARY
language:
C++14 (gcc 8.3)
created:
5 years 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!