Is there anyone who can explain the DP approach of this question! I got AC by recursive method but i wanna know about DP solution. So please explain the DP part of that one.

you can look at my solution : https://www.hackerrank.com/contests/w28/challenges/lucky-number-eight/submissions/code/1300062791

property of division of 8 is that it’s last 3 digits are divisible by 8.At first i have counted all 1 len and 2 length subsequences and then for 3 onwards calculated using dp.

specifically in my solution,dp1[k][i] denotes subsequences whose (last 1 digit 8 )=k,dp2[k][i] denotes subsequences whose (last 2 digits 8 )=k and same for dp3.

Sorry your solution is complicated to understand! Can you please elaborate more! Basically from this part dp2[i][(k*10+to(s[i]))%8]

The number is formed by concatenating the non-contiguous subsequences, which implies that the number itself is a subsequence and vice-versa.

So the problem boils down to counting the ways you can make a subsequence divisible by 8. This can be done by Dynamic Programming. At any position of the sequence, you need to consider two cases:

```
1. Concatenate the digit at the position with your current subsequence and move to next position.
2. Leave the digit and move to next position.
```

The idea can be coded with states: Current position and Remainder of the subsequence modulo 8.

@bansal1232 this is the code of problem lucky number eight.

```
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int len;
char buf[200010];
int f[200010][8];
void add(int& a , int v)
{
a += v;
if(a >= mod)a -= mod;
}
int main()
{
scanf("%d" , &len);
scanf("%s" , buf + 1);
f[0][0] = 1;
for(int i = 1 ; i <= len ; i++)
{
for(int j = 0 ; j < 8 ; j++)
add(f[i][j] , f[i - 1][j]);
for(int j = 0 ; j < 8 ; j++)
add(f[i][(j * 10 + buf[i] - '0') % 8] , f[i - 1][j]);
}
int ans = f[len][0];
ans = (ans - 1 + mod) % mod;
printf("%d\n" , ans);
return 0;
}
```

The editorial for this problem is also available you can also see that. I have seen the editorial, (the code is so small of about 8-9 lines) but I don’t think I should post the editorialist’s code.

first 2 nested for loops are just to calculate 1 length and 2 length arrays.From next it is for len>=3.

dp1[i][to(s[i])%8]+=powmod(2,i-1,MOD) denotes there are these many subsequences whose last 1 digit gives reminder (s[i]%8).

dp2[i][(k*10+to(s[i]))%8] denotes there are these many subsequences whose last 2 digits gives reminder (s[i]%8).

ex. (1234 here last two digits are 34 and it gives reminder (34%8));

dp2[i][(k*10+to(s[i]))%8]+=dp1[i-1][k] is I am conacatenating s[i] with all subsequences whose last 1 digit gives reminder k and their last index <i .Now int these subsequnces,last 2 digti gives reminder k*10+s[i] as string will be like …ks[i].Then I am taking cummulative sum and doing the same for 3 length subsequences. adding all 3 length subsequnces to previous answer.

Tell me one thing that how can you concatenate digits by multiplying 10 into (1,2,3,…7) ?

Let s be the given string of digits and n be the length of this string.

Consider f(i, j) as a function which is the number of subsequences upto position i (1-indexed) which when represented as a number and divided by 8 give remainder j. At each position i, we can either take the current digit into a subsequence, or ignore it.

If we ignore a digit s[i], the number of subsequences which give j modulo 8 would be simply f(i-1, j).

If we choose to take the digit s[i], the number of subsequences which give j modulo 8 are the sum of f(i-1, k), for all such k where (k \times 10+s[i]) \% 8=j. This is because when we append a digit d to an existing number S, the following holds: (S \times 10 +d) \% 8 = ((S \% 8) \times 10 + d) \% 8. This is the tricky part which took me a while to grasp.

Our answer is then f(n, 0) - 1, because we must exclude the empty subsequence which will be considered divisble by 8.

While computing however, one can be a little clever to avoid running a loop to find the required k values for each i, j… by simply running separate loops for j and k. (Or put them the same loop, at the price of losing clarity)

m = 1000000007 dp = 2D array of size (n+1)×8 dp[0][0] = 1 // empty subsequence equivalent to 0; 0 modulo 8 is 0 for i in [1..n]: for j in [0..7]: dp[i][j] += dp[i-1][j] // ignore s[i] for k in [0..7]: // working separately for each k dp[i][(k*10+s[i])%8] += dp[i-1][k] // include s[i] for j in [0..8]: dp[i][j] %= m // maintain modulo 10^9 + 7

The required answer is then `(dp[n][0] - 1 + m) % m`

.

Complexity is \mathcal{O}(8 \times n) which is \mathcal{O}(n).

Accepted code in Python3 here.

Feel free to ask if something isn’t clear

Please explain that tricky part in detail! I mean how did you able to deduce this with just single line formula?

@bansal1232 that particular line is just modular arithmetic. Suppose I have the input as “21533”, and consider we are at i=5 and k=1. Then by definition f(i-1, k) = f(4, 1) will the number of sequences upto position 4 which give 1 as remainder when divided by 8. These are “1”, “25”, “153” and “2153” so f(4, 1) = 4. At i=5 I find the digit 3, so s[i]=3. So if I append 3 to each of these sequences, the remainder of the new sequences would be

(1×10+3)%8 = 13%8 = 5

(25×10+3)%8 = 253%8 = 5

(153×10+3)%8 = 1533%8 = 5

(2153×10+3)%8 = 21533%8 = 5

As you can see both are the same as `(k*10+s[i])%8`

where the k=1 and s[i]=3. So basically the logic behind this is that appending 3 to all the sequences that give 1 modulo 8 will now give 5 modulo 8. So it’s clear that f(4, 1) is a part of f(5, 5).

Similarly f(4, 5) also contributes to f(5, 5) as (5×10+3)%8 = 5. And finally f(i-1, j) always contributes to f(i,j) so f(4,5) will again be considered into f(5,5). In the end f(5, 5) = f(4, 1) + f(4, 5) + f(4, 5).

I hope this example clarifies things somewhat!

#define MOD 1000000007

#define MAXN 200000

long long F[2][8];

char S[MAXN+10];

int main()

{

int N;

scanf("%d", &N);

scanf("%s", S);

```
int digit;
bool pre = 0;
bool cur = 1;
for (size_t i = 0; i < N; ++i) {
digit = S[i] - '0';
// here we do not consider S[i] so we just copy the previous value.
for (int k = 0; k < 8; ++k) {
F[cur][k] = F[pre][k];
}
// here we consider S[i], and only S[i] as a subsequence (length = 1)
++ F[cur][digit % 8];
// here we add S[i] to all the subsequence and find the new remainder(val%8) and update
// the respective remainder. So, after this step number of subsequence giving remainder
// j(from 0-8) will change.
// eg: 968
// s[i]=9. no of subsequence giving remainder 1 is 1
// s[i] 6. no of subsequence giving remainder 1 is 1, no of subsequence giving remainder
// 6 is 1, no of subsequence giving remainder 0 is 1(that is 96). and so on
for (int k = 0; k < 8; ++k) {
F[cur][(k * 10 + digit) % 8] += F[pre][k];
F[cur][(k * 10 + digit) % 8] %= MOD;
}
pre = !pre;
cur = !cur;
}
printf("%lld\n", F[pre][0] % MOD);
}
```

PS: JUST REMEMBER that dp[i][j] stores number of subsequence of giving the remainder j.let the subsequence be abcd and it gives a remainder x. we add e to the subsequence abcd and it becomes abcd*10+e =abcde. take the modulo. (abcde)%mod or (abcd*10+e)%mod or (x*10+e)%mod.

recursive method: https://www.hackerrank.com/contests/w28/challenges/lucky-number-eight/submissions/code/1300465668

long long int fun(int idx,int m)

{

if(idx>=n)

return (m==0)%MOD;

if(dp[idx][m]!=-1)

return (dp[idx][m])%MOD;

long long int ans=fun(idx+1,m)%MOD;

ans+=(fun(idx+1,(m*10+(ar[idx]-‘0’))%8))%MOD;

return dp[idx][m]=(ans)%MOD;

}