Problem Link

Here is my approach to MEXUM, I hope it might help you.

Try to think in reverse, how many subsequences will be there with MEX = 1, 2, and so on.

So, let us try to analyze small cases and form a pattern.

Let n = Total number of elements and

cnt1 = Total elements with count = 1.

cnt2 = Total elements with count = 2.

ans so on.

Now for MEX = 1:

Num_of_subs = (Any of n - cnt1)

→ Num_of_subs = 2^(n - cnt1) .

for MEX = 2:

Num_of_subs = (Atleast 1 of cnt1) * (Any of n - cnt1 - cnt2) .

=> Num_of_subs = [ { 2^(cnt1) - 1 } * { 2^(n - cnt1 - cnt2) } ].

for MEX = 3:

##
Try to think on your own

Num_of_subs = (Atleast 1 of cnt1) * (Atleast1 of cnt2) * (Any of n - cnt1 - cnt2 - cnt3) .

=> Num_of_subs = [ { 2^(cnt1) - 1 } * { 2^(cnt2) - 1 } * { 2^(n - cnt1 - cnt2 - cnt3) } ].

And so on until you don’t get a break in consecutive numbers from 1 to Current_MEX.

##
Why?

Because the smallest positive integer, not present can be the maximum MEX we can achieve.

**Submission Link**

The solution is messy because I had to debug it for a long time.

5 Likes

I was struggling to in debugging.but I was failed can you take a quick look at my code and tell me what’s wrong.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long int lt;

typedef vector vi;

typedef vector vin;

typedef pair<ll,ll> pll;

typedef pair<int,int> pin;

#define all(a) a.begin(),a.end()

#define rep(i,a,b) for(int i=a;i<b;++i)

#define f(i,b) for(int i=0;i<b;++i)

#define per(i,a,b) for(int i=a;i>=b;–i)

#define test(t) int t; cin>>t; while(t–) solve()

#define endl “\n”

#define p1 cout<<“YES”<<endl

#define p0 cout<<“NO”<<endl

#define fst ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

ll mod_pow(ll a,ll n,ll mod) //(a^n)%mod

{ ll res=1;

while(n){ if(n&1) res=(res*a)%mod; n/=2; a=(a*a)%mod; }

return res;

}

void solve();

int main()

{

fst;

test(t);

//solve();

}

/**********************<=“Actual code strats here”=>*****************************/

const int mod=998244353;

const int maxn=1e5+5;

int f[maxn];

void solve()

{

ll n;

cin>>n;

```
memset(f,0,sizeof f);
rep(i,0,n)
{
ll x;
cin>>x;
if(x<maxn)
f[x]++;
}
ll sum=1,sum2=1;
int i=1;
int cnt=1;
while(1)
{
sum+=sum2*(i*(mod_pow(2,n-f[i],mod)-cnt));
sum%=mod;
sum2*=mod_pow(2,f[i],mod)-1;
sum2%=mod;
n-=f[i];
if(f[i]==0)
{
break;
}
i++;
cnt=0;
}
cout<<sum<<endl;
```

}

`sum2*(i*(mod_pow(2,n-f[i],mod)-cnt))`

probably overflows

3 Likes

sum+=sum2*(i*(mod_pow(2,n-f[i],mod)-cnt));

Better write each term sepeartely and take modulo then multiply.

and after subtracting add modulo before taking mod.

sum2*=mod_pow(2,f[i],mod)-1;

sum2%=mod;

Here also same After subtracting 1, You should

add mod before taking modulo.

sum2*=mod_pow(2,f[i],mod)-1; sum2 += mod;

sum2%=mod;

I think this should work.

2 Likes

that was it.

feeling stupid right now.

I followed same approach .Please help , where my code failed :

```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
const ll N = 1e5+10;
ll a[N];
ll coun[N];
ll pref[N],mul[N],p2[N];
int main()
{
ll t,n,i,j,ans,val,temp,res,sum,v,mx;
p2[0]=1;
for(i=1;i<N;++i)
p2[i] = (p2[i-1]*2)%MOD;
cin>>t;
while(t--)
{
cin>>n;
for(i=0;i<=(n+2);++i)
coun[i]=pref[i]=mul[i]=0;
for(i=1;i<=n;++i)
{
cin>>a[i];
if(a[i]<=(n+1))
++coun[a[i]];
}
sum = 0;
res = 0;
//cout<<n<<"\n";
for(i=1;i<=(n+1);++i)
{
pref[i] = (pref[i-1] + coun[i])%MOD;
v = ((n - pref[i])%MOD)%MOD;
v = p2[v];
if(i==1)
{
res = (res+v)%MOD;
mul[i] = p2[coun[i]]-1;
}
else
{
res = (res + (v*(mul[i-1]*i)%MOD)%MOD)%MOD ;
v = p2[coun[i]]-1;
mul[i] = (v*mul[i-1])%MOD;
}
}
res = (res+MOD)%MOD;
cout<<res<<"\n";
}
return 0;
}
```

why we should add mod before subtracting 1?

I mean to say what problems it can cause?

if(!done){

int temp = product * num; temp %= MOD;

ans += temp; ans %= MOD;

}

```
if(!mp.count(1))
ans++, ans %= MOD;
```

What is the purpose of these two statements?

Consider a = 2, b = 4.

Now if you (2 - 4) % 4

We get output in negative. i.e -2.

So this might result in wrong answer.

So, its consider good practice to add modulo whenever subtracting to make answer positive.

1 Like

You can check it further here.

Link

I would say it was some debugging I had to do and added conditions as my code was giving the wrong answer.

if all the given numbers are in order 1 2 3 …n

we have consider n+1 which is ans for all subarrays which contains numbers from 1 to n

1 Like

consider

1 1 2 3 1 2

map will only contain numbers from 1 to 3

but we have to consider 4 as it could be the answer

So basic condition is that whenever you find number with frequency zero break

1 Like