PROBLEM LINK: BOMB

Setter: Blackrise (Saurabh Kishore Tiwari)

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic Programming, Combinatorics.

EXPLANATION

Since the strength of each warrior will be between {0} - {9}, we can calculate the frequency of each digit.

Now, all we need to do is generate all different numbers and store its mod value with {Z}. For this, we consider a dp[n][z].

For every universe, you travel all 10 digits and use the mod value calculated in the previous state to find out the number of possible answers for the current state using the given loop

```
for (int i = 0; i < 10; i++) dp[1][i % z] += freq[i];
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 10; j++) {
if (freq[j] == 0) continue;
for (int k = 0; k < z; k++) {
int temp = k * 10 + j;
temp %= z;
dp[i][temp] += (long) freq[j] * dp[i - 1][k];
}
}
}
```

Once we have done this, we know the power of all possible monsters. Print the number of monsters with power less than equal to {P}.

Time Complexity: {O} {(} {N} x {10} x {Z} {)}

Space Complexity: {O} {(} {N} x {Z} {)}

Problem Setter Code: Solution