AtCoder Beginner Contest 164

D - Multiple of 2019

Problem Statement: here

Solution: 

We are told to find out the number of pairs such that the base 10 representation of the string gets divisible by 2019. 

The problem could have been asked for any number, nothing special about 2019. Also, the problem could have been asked for any remainder,  like give those pairs which give the remainder of 1. 

So, basically, looking at the limit of N, going up to order 5, we can not create a 2D dp array. 

I claim that you don't need your dp array to the size above 2019. 

My main logic is: Gather the number of pairs up to the index i-1, which gives the remainder as 0,1,2,....2018 when divided by 2019. So, if I store their count in my dp array, then:

dp[i] represents the number of pairs which gives i when the number is modulo by 2019. I don't care what the number is, I just need the modulo. 

But. wait. Why? 

So, let us assume that the number is x up to the index i-1. Then, including the index i, the number will become 10*x + num[i] where num[i] is the digit of index i. To find it's remainder I will simply modulo it by 2019, which becomes (10*(x%2019) + num[i])%2019. So, we see that we don't require the number x, we just need the value of x%2019. 

So, I loop over all the possible values up to 2019, check if the dp[i] > 0, if yes then obtain the remainder when divided by 2019, if the remainder is 0: this means I can create exactly dp[j] answers, because dp[j] is the number of guys ending at index [i-1] giving remainder j, in front of whom, I can add this digit to get my answer. 

I have created another table inside the loop for each particular index, because I want to propagate the count of only those numbers of pairs which ended at current index giving the remainder. So, I copy it after the entire operation is done. 

The way I fill this inner dp table is simply : when I computed the remainder , I just do :

inner dp [ rem ] += dp[j] because I can get dp[j] pairs with this remainder, using similar logic by which we computed answer. 

The code:

void solve() { string s; cin >> s; ll ans = 0; ll dp[2019]; clr(dp,0); dp[s[0] - '0'] = 1; rep(i,1,s.size()){ int d = s[i] - '0'; ll tdp[2019]; clr(tdp,0); tdp[d] = 1; rep(j,0,2019){ if (dp[j] > 0){ ll rem = (10*j + d)%2019; if (rem == 0) ans+=dp[j]; tdp[rem]+=dp[j]; } } rep(i,0,2019){ dp[i] = tdp[i]; } } cout << ans; }