No.2302 Carry X Times
タグ : / 解いたユーザー数 65
作問者 :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。