No.2413 Multiple of 99
タグ : / 解いたユーザー数 39
作問者 :
AngrySadEight
/ テスター :
Ricky_pon
hamamu
問題文
非負整数 $x$ に対して，$10$ 進法での各桁の和を $d(x)$ と表します．
$0$ 以上 $10^N$ 未満の整数の中で，$99$ の倍数であるものを，上品な数と呼びます．
上品な数全体の集合を $X$ とします．このとき，$X$ に含まれるすべての $x$ に対する，$d(x)$ の値を $K$ 乗したものの総和を $998244353$ で割った余りを求めてください．
すなわち，$\sum_{x \in X} \{d(x)\}^K$ を $998244353$ で割った余りを求めてください．
制約
- 入力はすべて整数である．
- $2 \leq N \leq 10^5$
- $1 \leq K \leq 10^5$
入力
入力は以下の形式で標準入力から与えられる．
$N$ $K$
出力
答えを出力せよ．
サンプル
サンプル1
入力
2 2
出力
324
上品な数は，$0$ と $99$ のみです．
$d(0) = 0, d(99) = 18$ なので，求める値は $0^2 + 18^2 = 324$ となります．
サンプル2
入力
3 1
出力
180
上品な数は，$0, 99, 198, 297, 396, 495, 594, 693, 792, 891, 990$ の $11$ 個です．これらのうち，$0$ のみ各桁の和が $0$ で，それ以外の $10$ 個は各桁の和は $18$ です．
したがって，求める値は $0^1 \times 1 + 18^1 \times 10 = 180$ となります．
サンプル3
入力
14 2013
出力
212631289
$998244353$ で割った余りを求めてください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。