WA in MEXUM ( HELP )

https://www.codechef.com/viewsolution/32272069
This only passes the first task in Subtask 1 , which makes me believe my approach is correct but my implementation is wrong.

I calculate ans as,
ans = 1*( 2^{(cnt of elements \gt 1)} ) + 2*( 2^{(cnt of elements > 2)} ) * (2^{(number of 1s)}-1) + 3*( 2^{(cnt of elements > 3)} ) * (2^{(number of 1s)}-1) * (2^{(number of 2s)}-1) + .... until we find a number not present in the sequence.

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

const ll mod  = 998244353;
const db eps  = 1e-9 ;
const ll maxn = 1e9+1;
const ll inf = LLONG_MAX;

#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl

ll bin_power_mod(ll base, ll power, ll m) 
{
    base %= m;
    ll res = 1;
    while (power > 0) {
        if (power & 1)
            res = res * base % m;
        base = base * base % m;
        power >>= 1;
    }

    return res;
}

void solve()
{
    ll n , ans = 0 , multi = 1 , total =0;
    cin >> n;

    set<ll> s;
    map<ll,ll> cnt;

    for(ll i=0,tmp ; i<n ; ++i)
    {
        cin >> tmp;
        s.insert(tmp);
        cnt[tmp]++;
    } 

    for( ll i=1 ; i < maxn ; ++i)
    {
        if( s.find(i) != s.end() )
        {
            total += cnt[i];
            ans += (i*( bin_power_mod( 2LL , n-total , mod)*multi)%mod)%mod;
            multi *= ( bin_power_mod(2LL ,cnt[i] , mod)- 1) ; 

            ans%=mod , multi%=mod;
        }
        else
        {
            ans += (i*(bin_power_mod( 2 ,n-total , mod)*multi)%mod)%mod;
            ans%=mod ;

            cout << ans << endl;
            return;
        }
    } 

    return;

}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif

    ll t;
    cin >> t;

    while(t--)
    {
        solve();       
    }

    return 0;
} 

The bracketing on lines 52 and 59 is your problem.

(a*(b*c)%m)%m is the same as ((a*b*c)%m)%m because of precedence. What you want is (a*(b*c%m))%m

Modified AC code

1 Like
3 Likes

Damn, Lost my AC just because of some missing parenthesis. Thanks :slight_smile:

Thanks, didn’t knew about this. I knew I was messing up the modulo somehow but just couldn’t figure it out during the contest.