Another Meme Problem
Contest: Educational Codeforces Round 68 (Rated for Div. 2)
Difficulty rating: 2700
Tags: dp

Let's call a fraction $$$\frac{x}{y}$$$ good if there exists at least one another fraction $$$\frac{x'}{y'}$$$ such that $$$\frac{x}{y} = \frac{x'}{y'}$$$, $$$1 \le x', y' \le 9$$$, the digit denoting $$$x'$$$ is contained in the decimal representation of $$$x$$$, and the digit denoting $$$y'$$$ is contained in the decimal representation of $$$y$$$. For example, $$$\frac{26}{13}$$$ is a good fraction, because $$$\frac{26}{13} = \frac{2}{1}$$$.

You are given an integer number $$$n$$$. Please calculate the number of good fractions $$$\frac{x}{y}$$$ such that $$$1 \le x \le n$$$ and $$$1 \le y \le n$$$. The answer may be really large, so print it modulo $$$998244353$$$.

Input format:
The only line of the input contains one integer $$$n$$$ ($$$1 \le n < 10^{100}$$$).

Output format:
Print the number of good fractions $$$\frac{x}{y}$$$ such that $$$1 \le x \le n$$$ and $$$1 \le y \le n$$$. The answer may be really large, so print it modulo $$$998244353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
42

Example output:
150

Example input:
3141592653589793238462643383279

Example output:
459925407

Editorial:
Let's fix an irreducible fraction $$$\frac{X}{Y}$$$ such that $$$1 \le X, Y \le 9$$$. Obviously, each good fraction is equal to exactly one of such irreducible fractions. So if we iterate on $$$X$$$ and $$$Y$$$, check that $$$gcd(X, Y) = 1$$$ and find the number of good fractions that are equal to $$$\frac{X}{Y}$$$, we will solve the problem.
Okay, suppose we fixed $$$X$$$ and $$$Y$$$. Any good fraction can be represented as $$$\frac{zX}{zY}$$$, where $$$z$$$ is some positive integer. Let's try all possible values of $$$z$$$, and for them check whether they correspond to a good fraction.
How do we try all values of $$$z$$$ without iterating on them? Let's construct the decimal representation of $$$z$$$ from the least significant digit to the most. As soon as we fix $$$k$$$ least significant digits of $$$z$$$, we know $$$k$$$ least significant digits of $$$zX$$$ and $$$zY$$$. So let's try to use digit DP to try all possible values of $$$z$$$.
Which states do we have to consider? Of course, we need to know the number of digits we already placed, so that will be the first state. After we placed $$$k$$$ digits, we know first $$$k$$$ digits of the numerator of the fraction; but to get the value of digit $$$k + 1$$$, knowing only the value of the corresponding digit in $$$z$$$ is not enough: there could be some value carried over after multiplying already placed digits by $$$X$$$. For example, if $$$X = 3$$$, and we placed the first digit of $$$z$$$ and it is $$$7$$$, we know that the first (least significant) digit of $$$zX$$$ is $$$1$$$, and we know that after fixing the second digit of $$$z$$$ we should add $$$2$$$ to it to get the value of this digit in $$$zX$$$, since $$$2$$$ is carried over from the first digit. So, the second state of DP should represent the number that is carried over from the previous digit in the numerator, and the third state should do the same for the denominator.
Okay, in order to know whether the fraction is good, we have to keep track of some digits in the numerator and denominator. If $$$\frac{x'}{y'} = \frac{X}{Y}$$$, $$$1 \le x' \le 9$$$ and $$$1 \le y' \le 9$$$, then we have to keep track of the digit representing $$$x'$$$ in the numerator and the digit representing $$$y'$$$ in the denominator. So we have two additional states that represent the masks of "interesting" digits we met in the numerator and in the denominator.
The only thing that's left to check is that both $$$zX$$$ and $$$zY$$$ are not greater than $$$n$$$. Let's construct the decimal representation of $$$n$$$ and prepend it with some leading zeroes; and keep constructing the numerator and the denominator until they have the same number of digits as the decimal representation as $$$n$$$. Then we can compare the representation of, for example, numerator with the representation of $$$n$$$ as strings. Comparing can be done with the following technique: let's keep a flag denoting whether the number represented by the least significant digits of the numerator is less or equal than the number represented by the same digits from $$$n$$$. When we place another digit of the numerator, we can get the new value of this flag as follows: if new digit of the numerator is not equal to the corresponding digit of $$$n$$$, then the value of the flag is defined by comparing this pair of digits; otherwise the value of the flag is the same as it was without this new digit. Of course, we should do the same for the denominator.
Okay, now we can actually start coding this DP: $$$dp[k][carry1][carry2][comp1][comp2][mask1][mask2]$$$ is the number of possible ways to put $$$k$$$ least significant digits in $$$z$$$ in such a way that:
• the value carried over to the next digit of the numerator is $$$carry1$$$ (and $$$carry2$$$ for the denominator);
• $$$comp1$$$ denotes whether the current numerator is less or equal to the number represented by $$$k$$$ least significant digits of $$$n$$$ ($$$comp2$$$ does the same for the denominator);
• $$$mask1$$$ denotes which "interesting" digits we already met in the numerator (of course, $$$mask2$$$ does the same for the denominator).
If you are feeling confident in your programming abilities, you can just start implementing this DP on a seven-dimensional array. I was too afraid to do it (but, looking at participants' solutions, I realize that it sounds much more scary than it looks in the code), so I decided to write the model solution using a structure representing each state, and a map to store all these structures. This is a common technique: when a dynamic programming solution you come up with has some really complex states and transitions, it is sometimes better to use some self-implemented structures to define these states and store them in a map or a hashmap. Some advantages of this technique are:
• it's sometimes much easier to code (the code may be longer than the same solution with regular DP stored in a multi-dimensional array, but it's easier to write and understand this code);
• if most states are unreachable, they won't even appear in our map, so we skip them altogether;
• it is easy to add some optimizations related to reducing the number of states. For example, the number of different values for $$$mask1$$$ and $$$mask2$$$ may be too much, so we can use the following optimization: as soon as we find some pair of numbers in $$$mask1$$$ and $$$mask2$$$ that can represent $$$x'$$$ and $$$y'$$$, we can change these masks to some values that will mark that they are "finished" and stop updating them at all.