PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Jubayer Nirjhor
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Combinatorics and fundamental counting principle
PROBLEM:
Given an array A of N positive integers, we define f(S) as the mex of subsequence S. Find the sum of f(S) over all subsequences of A.
QUICK EXPLANATION
- The mex of a subsequence of length N cannot exceed N. So we can replace all elements greater than N with N.
- Fixing the value of mex, letās try to count the number of subsequences with specific mex.
- For a given mex, we need each positive value smaller than mex to be present at least once, value mex shouldnāt be present, and values greater than mex do not affect us.
- If f_x denote the frequency of value x, the number of non-empty subsets of these f_x elements is 2^{f_x}-1. We need to select one of the subsets for each x less than current mex, giving us \displaystyle\prod_{x = 1}^{mex-1} 2^{f_x} -1
- To consider elements greater than mex, we can take any subset of those. If there are y elements greater than mex, it contributes 2^y subsets for each choice of subsets of smaller values.
EXPLANATION
First thoughts tell us that mex of an array of length N cannot exceed N+1. The proof is easy, just try to build an array with mex N+2
Letās try fixing the value of mex, say M such that 0 \leq M \leq N is the current mex, and trying to count the number of subsequences with mex M. Say the number of subsequences is A, it contributes M*A to the sum of mex of subsequences.
Now, for mex M, we need each value 1 \leq x < M to be present at least once. Let f_x denote the frequency of x in A.
For each x to be present once, we can visualize it as a set with f_x elements and we need to count the number of ways to select a non-empty subset, which we know, is 2^{f_x}-1
Since the choice of subset for each x is independent of other x, by fundamental counting principle, the number of ways of choosing values smaller than M such that each value is present at least once is \displaystyle\prod_{x = 1}^{M-1} 2^{f_i}-1
Now, we know that M cannot appear in subsequence. Suppose g_M denotes the number of elements greater than M, each choice of a subset of g_M elements is valid. We get 2^{g_M} choices.
Hence, the final answer can be written as \displaystyle\sum_{M = 1}^{N+1} M*2^{g_M} *\prod_{x = 1}^{M-1} 2^{f_i}-1
For implementation, sorting the elements would make things easier. Refer to my code for more details.
TIME COMPLEXITY
The time complexity is O(N*log(N)) per test case due to sorting as well as computing powers.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;
const int MOD = 998244353;
int t, n;
ll two[N], a[N], freq[N], sf[N];
int main() {
two[0] = 1;
for (int i = 1; i < N; ++i) two[i] = 2 * two[i - 1] % MOD;
cin >> t;
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%lld", a + i);
++freq[min(a[i], n + 1LL)];
}
sf[n + 69] = 0;
for (int i = n + 68; i; --i) sf[i] = sf[i + 1] + freq[i];
ll ans = 0, pf = 1;
for (ll i = 1; i <= n + 1; ++i) {
ans = (ans + i * (pf * two[sf[i + 1]] % MOD)) % MOD;
pf = pf * (two[freq[i]] - 1) % MOD;
}
ans += MOD, ans %= MOD;
printf("%lld\n", ans);
for (int i = 0; i <= n + 69; ++i) freq[i] = 0;
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (998244353)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
#define int ll
int a[123456],two[123456];
map<int,int> mapi;
signed main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int i;
two[0]=1;
f(i,1,123456){
two[i]=two[i-1]*2;
two[i]%=mod;
}
int t;
cin>>t;
while(t--){
mapi.clear();
int n;
cin>>n;
int i,maxi=0;
rep(i,n){
cin>>a[i];
mapi[a[i]]++;
maxi=max(maxi,a[i]);
}
mapi[maxi+1]=0;
int previ=0,sofar=0;
int befor=1,ways,tot=0;
map<int,int>::iterator it;
for(it=mapi.begin();it!=mapi.end();it++){
if(it->ff==previ+1){
ways=two[n-sofar-(it->ss)];
ways*=befor;
ways%=mod;
ways*=(it->ff);
ways%=mod;
tot+=ways;
tot%=mod;
previ=it->ff;
}
else{
ways=two[n-sofar];
ways*=befor;
ways%=mod;
ways*=(previ+1);
ways%=mod;
tot+=ways;
tot%=mod;
break;
}
sofar+=it->ss;
befor*=(two[it->ss]-1);
befor%=mod;
}
cout<<tot<<endl;
}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class MEXUM{
//SOLUTION BEGIN
long MOD = 998244353;
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
long[] a = new long[n];
for(int i = 0; i< n; i++)a[i] = nl();
Arrays.sort(a);
long ans = 0;
long ways = 1;
int prev = 0;int idx = 0;
for(int mex = 1; mex <= n; mex++){
while(prev+1 < mex){
int cnt = 0;
while(idx < n && a[idx] == prev+1){
idx++;
cnt++;
}
ways = mul(ways, add(pow(2, cnt), MOD-1));
prev++;
}
int pos = idx;
for(int p = idx; p < n && a[p] == mex; p++)pos++;
ans = add(ans, mul(mex, ways, pow(2, n-pos)));
}
pn(ans);
}
long pow(long a, long p){
long o = 1;
for(; p>0; p>>=1){
if((p&1)==1)o = mul(o, a);
a = mul(a, a);
}
return o;
}
long add(long... a){
long o = 0;
for(long x:a)o = (o+MOD+x)%MOD;
return o;
}
long mul(long... a){
long p = 1;
for(long x:a)p = (MOD+(p*x)%MOD)%MOD;
return p;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new MEXUM().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
