問題一覧 > 通常問題

No.2302 Carry X Times

レベル : / AI推定難易度 : 1925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 65
作問者 : Shirotsume / テスター : 👑 AngrySadEight ygussany
お気に入りにしたユーザー ProblemId : 9465 / 自分の提出
問題文最終更新日: 2023-05-03 01:56:18
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. Back to the original
yukicoder contest 388 (順位表) の他の問題:

Problem Statement

You are given integers $N, X$. Find the number, modulo $998244353$, of pairs $(a, b)$ of $2$ integers between $0$ and $N$, inclusive, such that exactly $X$ carries occur when computing $a + b$ by column addition in base ten.

You are given $T$ test cases; solve each of them.

Notes

When $a, b$ satisfy at least one of the following conditions, a carry occurs at the $10^i$ place when computing $a + b$ by column addition.

  • $i \geq 0$, and the sum of the $10^i$ digit of $a$ and the $10^i$ digit of $b$ is at least $10$.
  • $i \geq 1$, the sum of the $10^i$ digit of $a$ and the $10^i$ digit of $b$ is at least $9$, and a carry occurs at the $10^{i - 1}$ place.

The number of carries is defined as the number of digit positions at which a carry occurs.

Constraints

  • All input values are integers.
  • $1 \leq T \leq 10$
  • $1 \leq N \leq 10^{18}$
  • $0 \leq X \leq 18$

Input

The input is given from Standard Input. The $1$st line contains the number of test cases $T$.

$T$

Each of the following $T$ lines, starting from the $2$nd line, contains a test case in the following format.

$N$ $X$

Output

Output the answer.

Sample

Sample 1
Input
10
10 1
60 2
1 1
12345 4
192837465 7
31415926535897932 10
1000000000000000000 18
913735795884242535 0
395391555195826443 1
878726973525897581 14
Output
45
135
0
8405325
677685118
291532276
223705214
934722789
676277431
526128107

$10$ test cases are given.

  • $1$st test case: There are $45$ pairs $(a, b)$ of integers between $0$ and $10$, inclusive, for which exactly $1$ carry occurs, such as $(1, 9)$, $(7, 5)$, and $(8, 8)$.
  • $2$nd test case: There are $135$ pairs $(a, b)$ of integers between $0$ and $60$, inclusive, for which exactly $2$ carries occur, such as $(41, 59)$ and $(55, 55)$.
  • $3$rd test case: There are no pairs $(a, b)$ of integers between $0$ and $1$, inclusive, for which exactly $1$ carry occurs.

Note that for each test case, you are to find the answer modulo $998244353$.

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