問題一覧 > 通常問題

No.3304 INCREASE decrease

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 19
作問者 : sepa38 / テスター : dyktr_06 Nafmo2
お気に入りにしたユーザー ProblemId : 12411 / 自分の提出
問題文最終更新日: 2026-08-10 13:14:57
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. Show the original
yukicoder contest MMA Contest 020 (順位表) の他の問題:

Problem Statement

For positive integers $X, Y, Z$ satisfying $X < Y < Z < N$, let $x, y, z$ denote their last $K$ digits, respectively. Find the number of triples $X, Y, Z$ satisfying all of the following conditions.

  • $0 < Y - X = Z - Y$
  • $0 < x - y = y - z$
Since the answer can be very large, output it modulo $998244353$.
You are given $T$ test cases; find the answer for each of them.

Constraints

  • All input values are integers
  • $10 \leq N \leq 10^{18}$
  • $1 \leq K$
  • $10^K \leq N$
  • $1 \leq T \leq 10^5$

Input

The input is given from Standard Input in the following format. 
$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$
Each test case is given in the following format. 
$N \ K$

Output

Output the answer modulo $998244353$.

Sample

Sample 1
Input
3
21 1
2025 2
123456789012345678 9
Output
4
231310
889386892

For example, in the case $(N, K) = (21, 1)$, the triples $(X, Y, Z)$ satisfying the conditions are the $4$ triples $(2, 11, 20), (4, 12, 20), (6, 13, 20), (8, 14, 20)$. Considering $(2, 11, 20)$, we have $(X, Y, Z) = (2, 11, 20), (x, y, z) = (2, 1, 0)$, which satisfies $0 < 9 = 11 - 2 = 20 - 11$ and $0 < 1 = 2 - 1 = 1 - 0$.

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