### PROBLEM LINK:

**Author:** Utkarsh

**Tester:**

**Editorialist:** Jingbo Shang, Anudeep

### DIFFICULTY:

Easy

### PREREQUISITES:

Dynamic Programming

### PROBLEM:

Given a string **S** which has ‘0’ - ‘9’. Find number of substrings, which when represented in base 10, whose remainder under mod **M** equals to **L**.

### EXPLANATION:

Let **F*[j]** denote the number of substrings ended at **i**-th character and the value mod **M** equals to **j**.

Therefore, we can try to extend **F*[j]** to **F[i + 1][(j * 10 + S[i + 1]] % 10]** by simply add the next character. Or, one can also take the single character **i+1**-th into account.

So, we can formally have the algorithm as following:

- Initially,
**F*[S* % M]**is 1. Because we can only choose the single character. - Then,
**F[i + 1][(j * 10 + S[i + 1]] % 10] += F*[j]**, by extending substrings. - The final answer should be the sum of
**F[1…|S|][L]**.

This algorithm’s time complexity is **O(|S|L)**, which is efficient enough for this problem.

### AUTHOR’S AND TESTER’S SOLUTIONS:

The links will be fixed soon.

Author’s solution can be found here.

Tester’s solution can be found here.