問題一覧 > 通常問題

No.3304 INCREASE decrease

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : sepa38 / テスター : dyktr_06 Nafmo2
ProblemId : 12411 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-10-04 23:07:53

問題文

$X < Y < Z < N$ を満たす正整数 $X, Y, Z$ について、下 $K$ 桁をそれぞれ $x, y, z$ とおきます。 以下の条件をすべて満たす $X, Y, Z$ の組が何通りあるか求めてください。

  • $0 < Y - X = Z - Y$
  • $0 < x - y = y - z$
ただし、答えは非常に大きくなる可能性があるため、$998244353$ で割った余りを出力してください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 入力はすべて整数
  • $10 \leq N \leq 10^{18}$
  • $1 \leq K$
  • $10^K \leq N$
  • $1 \leq T \leq 10^5$

入力

入力は以下の形式で標準入力から与えられます。 
$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$
各テストケースは以下の形式で与えられます。 
$N \ K$

出力

$998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
3
21 1
2025 2
123456789012345678 9
出力
4
231310
889386892

例えば $(N, K) = (21, 1)$ のケースでは、条件を満たす $(X, Y, Z)$ の組は $(2, 11, 20), (4, 12, 20), (6, 13, 20), (8, 14, 20)$ の $4$ つです。 $(2, 11, 20)$ について考えてみると、$(X, Y, Z) = (2, 11, 20), (x, y, z) = (2, 1, 0)$ で、 $0 < 9 = 11 - 2 = 20 - 11$ および $0 < 1 = 2 - 1 = 1 - 0$ を満たしています。

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