One-child Numbers

We say that a $d$-digit positive number (no leading zeros) is a one-child number if exactly one of its sub-strings is divisible by $d$.
For example, $5671$ is a $4$-digit one-child number. Among all its sub-strings $5$, $6$, $7$, $1$, $56$, $67$, $71$, $567$, $671$ and $5671$, only $56$ is divisible by $4$.
Similarly, $104$ is a $3$-digit one-child number because only $0$ is divisible by $3$.
$1132451$ is a $7$-digit one-child number because only $245$ is divisible by $7$.
Let $F(N)$ be the number of the one-child numbers less than $N$.
We can verify that $F(10) = 9$, $F(10^3) = 389$ and $F(10^7) = 277674$.
Find $F(10^{19})$.

This problem appears to be from Project Euler (Problem 545). This is a combinatorics and number theory problem and requires a detailed understanding to solve.

Here’s a rough approach to this type of problem:

1. Define a `dp` array where `dp[i][j][k]` means the number of ways to form a `j` digit number where only one of its sub-strings is divisible by `d` (it has been taken modulo `d` is `i`), and it’s already been divided by `d`.

2. Initialize `dp` as `dp[0][0][0] = 1`.

3. For `i` from 0 to `d-1`, for `j` from 0 to `18`, for `k` from 0 to 1, calculate: `dp[(i*10^l+x)%d][j+1][1] += dp[i][j][k]` if `i*10^l+x` is divisible by `d` (where `x` is from `0` to `9`), else `dp[(i*10^l+x)%d][j+1][0] += dp[i][j][k]`.

4. Calculate the number of ways for each digit level for `10^19`.

The answer to this problem wouldn’t be feasible to calculate by hand due to the computational intensity, especially for large values like `10^19`. For such calculations, we typically use a programming language or a specific mathematics software. But this gives you an idea of how to tackle it.

More Answers: