問題一覧 > 通常問題

No.3089 Base M Numbers, But Only 0~9

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 62
作問者 : yuusaan / テスター : 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 11639 / 自分の提出
問題文最終更新日: 2025-04-05 02:56:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 463 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。