問題一覧 > 通常問題

No.2413 Multiple of 99

レベル : / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 39
作問者 : 👑 AngrySadEight / テスター : Ricky_pon hamamu
3 ProblemId : 9924 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-02 10:16:51

問題文

非負整数 xx に対して，1010 進法での各桁の和を d(x)d(x) と表します．

00 以上 10N10^N 未満の整数の中で，9999 の倍数であるものを，上品な数と呼びます．

上品な数全体の集合を XX とします．このとき，XX に含まれるすべての xx に対する，d(x)d(x) の値を KK 乗したものの総和を 998244353998244353 で割った余りを求めてください．

すなわち，∑x∈X{d(x)}K\sum_{x \in X} \{d(x)\}^K を 998244353998244353 で割った余りを求めてください．

制約

  • 入力はすべて整数である．
  • 2≤N≤1052 \leq N \leq 10^5
  • 1≤K≤1051 \leq K \leq 10^5

入力

入力は以下の形式で標準入力から与えられる．

NN KK

出力

答えを出力せよ．

サンプル

サンプル1
入力
2 2
出力
324

上品な数は，00 と 9999 のみです．

d(0)=0,d(99)=18d(0) = 0, d(99) = 18 なので，求める値は 02+182=3240^2 + 18^2 = 324 となります．

サンプル2
入力
3 1
出力
180

上品な数は，0,99,198,297,396,495,594,693,792,891,9900, 99, 198, 297, 396, 495, 594, 693, 792, 891, 990 の 1111 個です．これらのうち，00 のみ各桁の和が 00 で，それ以外の 1010 個は各桁の和は 1818 です．

したがって，求める値は 01×1+181×10=1800^1 \times 1 + 18^1 \times 10 = 180 となります．

サンプル3
入力
14 2013
出力
212631289

998244353998244353 で割った余りを求めてください．

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