問題一覧 > 通常問題

No.3566 Subsequence Sum

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 18
作問者 : 👑 to-omer / テスター : 👑 hamamu
お気に入りにしたユーザー ProblemId : 9889 / 自分の提出
問題文最終更新日: 2026-03-20 23:25:11
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 501 (順位表) の他の問題:

Problem Statement

You are given a positive integer $N$. Let $S$ be the string obtained by concatenating the decimal representation of $N$ $K$ times.
Find the sum of the set of numbers obtainable as subsequences of $S$, modulo $998244353$.

Here, a number obtainable as a subsequence is the number obtained by interpreting, as a decimal number, a non-empty string formed by deleting $0$ or more characters from the string and arranging the remaining characters in their original order. For example, the set of numbers obtainable as subsequences of 404 is $\{0,4,40,44,404\}$.

Constraints

  • All inputs are integers
  • $1\le N<10^{10^6}$
  • $1\le K\le 10^9$

Input

$N$
$K$

Output

Output the answer in 1 line.

Sample

Sample 1
Input
404
1
Output
492

The set of numbers obtainable as subsequences of 404 is $\{0,4,40,44,404\}$, and their sum is $492$.

Sample 2
Input
10
3
Output
160118

$S=$ 101010.

Sample 3
Input
1
1000000000
Output
678968756

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。