No.3089 Base M Numbers, But Only 0~9
タグ : / 解いたユーザー数 62
作問者 :
amentorimaru
Story
Worn out by their busy days, Yu-san started saying something strange.
"In a base greater than $10$, imagine if the digit after 9 were 0 instead of A. That would be a real mess. For example, doing that in base $12$ gives
$1,2,3,4,5,6,7,8,9,$$0$$,$$1$$,10,11,12,13,14,15,16,17,18,19,1$$0$$,1$$1$$,20,21,\dots$.
With this in mind, I came up with the following problem."
Problem Statement
For a positive decimal integer $x$ and an integer $y$ that is at least $10$ (these $x,y$ are written in decimal), convert $x$ to base $y$, and replace the digit that is the $j$-th smallest ($0$-indexed) among the digits used with $j\mod{10}$. We call the resulting digit string the ten-symbol base-$y$ notation of $x$.
More strictly, the ten-symbol base-$y$ notation of $x$ is defined by the following rules.
- Initially, let $S$ be an empty string, and repeat the following operation for $i=1,2,\dots$.
- If $x\ge y^{i-1}$, append $(\lfloor x/y^{i-1} \rfloor \mod{y})\mod{10}$ to the left of $S$.
- Otherwise, end the operation.
For example, $31$ satisfies $31=1F_{(16)}$, and since $1$ is the $1$-st smallest and $F$ is the $1$$5$-th smallest, its ten-symbol base-$16$ notation is $15$ .
$168$ satisfies $168 = A8_{(16)}$, and since $A$ is the $1$$0$-th smallest and $8$ is the $8$-th smallest, its ten-symbol base-$16$ notation is $08$ .
You are given a positive integer $M$ that is at least $10$ and a digit string $N$ in ten-symbol base-$M$ notation.
Let $x$ denote a positive decimal integer whose ten-symbol base-$M$ notation is $N$. Find the sum of all such $x$. (If no $x$ satisfies the condition, the sum is $0$.)
Since the answer can be extremely large, output the answer modulo $998244353$.
Input
$M$ $N$
Note that $M$ is given first.
Constraints
- $N$ is a digit string consisting of
0123456789, with length at least $1$ and at most $2\times 10^5$ - $10 \le M \le 10^{18}$
- $M$ is an integer
Output
Output the answer on one line, followed by a newline.
Sample
Sample 1
Input
13 21
Output
388
We have $27=21_{(13)},37=2B_{(13)},157=C1_{(13)},167=CB_{(13)}$.
All of $27,37,157,167$, and only these, have the ten-symbol base-$13$ notation $21$. Their sum is $388$.
Sample 2
Input
25 1
Output
33
All of $1,11,21$, and only these, have the ten-symbol base-$25$ notation $1$. Their sum is $33$.
Sample 3
Input
10 998244357
Output
4
Only $998244357$ has the ten-symbol base-$10$ notation $998244357$.
Note that you must output the value modulo $998244353$.
Sample 4
Input
998244352 314159265358979323846
Output
112653444
Note that $N$ can be an extremely large value when regarded as a decimal integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。