Problem 1105C - Ayoub and Lost Array
Solution 79970854

-What is the meaning of dp[i][j]

{ it gives us number of ways to get sum of first i numbers such that the ( sum till i) %3==j & j can be 0,1,2 }
lets break dp[i][0] in 3 cases
1.dp[i][0]+=dp[i-1][0]*range[0];
2.dp[i][0]+=dp[i-1][1]*range[2];
3.dp[i][0]+=dp[i-1][2]*range[1]; and so on..3 cases for mod=2 and 3 for mod=1

Discussing case 3

— (sum of first i-1 numbers) % 3 ==2 {this can be done in dp[i-1][2] ways}
— and current number which we select for position i has % with 3 == 1 {this can be done in range[1] ways}
— so in this way we have mod of overall sum of first i elements with 3 == 0
— and this can be done in (dp[i-1][2] ways)*(range[1] ways) { 3rd case only }
— so if we combine all 3 cases for dp[i][0],we get this ...
— dp[i][0] = dp[i-1][2]*range[1] + dp[i-1][1]*range[2] + dp[i-1][0]*range[0]

What is dp[0][0]

— number of ways to have a sum of the first i {i.e 0 here} numbers out of total n numbers
in such a way that sum%3 == j {i.e 0 here for dp[0][0]}

What is range[1]

range [1]=total numbers in range [l,r] having their % with 3==1 similarly range [0] & range [2] are calculated.