Differences between (a+=b)%p; and a =(a+b)%p;

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

I recently came across this problem while solving E1 of Codeforces Round 967 (Div. 2)

My original code used (a+=b)%p; and it worked perfectly with small test cases, but it gave WA when the test cases get larger. After i changed it to a =(a+b)%p; the code got accepted.

I'm a bit frustrated because it took me until after the contest was finished that i found the dumb mistake that probably stopped me from getting the Candidate Master title, so I made this post to discuss the differences between those 2 syntax to help people avoid the same mistake as me (and mostly just for me to vent T^T )

Here's my original code (Please don't pay attention to the dumb variable names hehe)

My Code

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

//#define int long long //emergency debug

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define hellnah cout<<"NO\n"
#define fuckyeah cout<<"YES\n"
#define en '\n'

const ll oo = 1e9;
int t;
int n,k,p;

//ll dp[505][505][505];
ll dp2[505][505];
//ll dp3[505][505];
ll c[505][505];
ll fac[505];


ll po(ll x, ll y){
    if(y==0) return 1;
    ll tmp  = po(x,y/2);
    if(y%2==0) return tmp*tmp%p;
    return tmp*tmp%p*x%p;
}

ll C(int u, int x){
    if(x==0||u==0) return 1;
    ll res = po(fac[x], p-2);
    ll N = (po(2,u)-1+x-1+p)%p;
    while(x--){
        res = res*N%p;
        N--;
    }
    return res;
}

void init(){
    fac[0] = 1;
    for(int i = 1;i<=k;i++) fac[i] = fac[i-1]*i%p;
    
    for(int i = 0;i<=n;i++)
        for(int j = 0;j<=k;j++) dp2[i][j] = 0, c[i][j] = C(i,j);
        
}

void work(){
    cin>>n>>k>>p;
    
    init();
    
    for(int i = 1;i<=k;i++) dp2[n][i] = 1;
    ll asdf;
    for(int i = n-1;i>0;i--){
        for(int j = 0;j<=k;j++)
            for(int z = j+1;z<=k-j;z++) asdf = c[n-i][j]*dp2[i+1][z]%p, dp2[i][j+z] = (dp2[i][j+z]+asdf*2%p)%p;

        //////////////////////////////////////////////////////////////////////////
        //////////////////////////////////////////////////////////////////////////
        for(int j = 2;j<=k;j++) (dp2[i][j]+=dp2[i][j-1])%p;// look at this line
        //////////////////////////////////////////////////////////////////////////
        //////////////////////////////////////////////////////////////////////////
        
    }
    cout<<dp2[1][k]<<en;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) work();
    return 0;
}
//flashbang

It only worked on test 1, and failed test 2. However, when i changed this line, it worked perfectly

//for(int j = 2;j<=k;j++) (dp2[i][j]+=dp2[i][j-1])%p;
for(int j = 2;j<=k;j++) dp2[i][j]=(dp2[i][j]+dp2[i][j-1])%p;

Can anyone explain why this single line broke my code? :(

Comments (5)

Write comment?

myst-6

4 months ago, # |

← Rev. 2 →

+25

Try for(int j = 2;j<=k;j++) (dp2[i][j]+=dp2[i][j-1])%=p;. Notice the equals sign after the mod ;)

→ Reply

PUSSY_LICKING_LOLI_69

4 months ago, # ^ |

Thanks it works now, but why does the one without the equal sign work with small numbers?

That's because the += operator goes, through, but the % operator doesn't do anything; its result is not assigned to anything.

macaquedev

-9

that is not very sigma

VitalyKo

Just because.. this shouldn't take mod and it's pretty logical

The result of the % operation is not assigned to anything

PUSSY_LICKING_LOLI_69's blog