No.2413 Multiple of 99
タグ : / 解いたユーザー数 39
作問者 : 👑
Ricky_pon
👑 
hamamu
Problem Statement
For a non-negative integer $x$, let $d(x)$ denote the sum of its digits in base $10$.
Among the integers at least $0$ and less than $10^N$, those that are multiples of $99$ are called elegant numbers.
Let $X$ be the set of all elegant numbers. Find the sum, over all $x$ contained in $X$, of the value of $d(x)$ raised to the power $K$, modulo $998244353$.
That is, find $\sum_{x \in X} \{d(x)\}^K$ modulo $998244353$.
Constraints
- All inputs are integers.
- $2 \leq N \leq 10^5$
- $1 \leq K \leq 10^5$
Input
The input is given from standard input in the following format.
$N$ $K$
Output
Output the answer.
Sample
Sample 1
Input
2 2
Output
324
The only elegant numbers are $0$ and $99$.
Since $d(0) = 0, d(99) = 18$, the desired value is $0^2 + 18^2 = 324$.
Sample 2
Input
3 1
Output
180
There are $11$ elegant numbers: $0, 99, 198, 297, 396, 495, 594, 693, 792, 891, 990$. Among these, only $0$ has a digit sum of $0$, and the other $10$ have a digit sum of $18$.
Therefore, the desired value is $0^1 \times 1 + 18^1 \times 10 = 180$.
Sample 3
Input
14 2013
Output
212631289
Find the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。