問題一覧 > 通常問題

No.2166 Paint and Fill

レベル : / AI推定難易度 : 3325 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 10
作問者 : NyaanNyaan / テスター : 👑 Nachia
お気に入りにしたユーザー ProblemId : 8867 / 自分の提出
問題文最終更新日: 2022-12-18 16:30:35
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
Advent Calendar Contest 2022 (順位表) の他の問題:

Note

This problem has a strict time limit, so using a fast language is strongly recommended.
The writer's solution and the tester's solution are both written in C++, and their execution times are 3000 ms and 3519 ms, respectively.

Hint: Time complexity of the intended solution (added at 13:30) The time complexity of the intended solution is $\mathrm{O}(\min(X \log^2 X, T \sqrt{L} \log{L}))$, where $X = T + \max(K_i), L = \min(\mathrm{mod}, \max(K_i))$.

Problem Statement

There is a grid with $2 \times N$ cells (height by width). Every cell of the grid is painted white.
You perform the following sequence of operations exactly 1 time.

  • Choose exactly $K$ cells of the grid and repaint the chosen cells red.
  • Then, write one number in each cell of the grid so that all of the following conditions are satisfied.
    • Every integer between $1$ and $N$, inclusive, appears exactly $2$ times.
    • Each white cell in the $j$-th column from the left has $j$ written in it.
Find the number of possible states of the grid after the operations, modulo $\text{mod }998244353$.
Here, two states of the grid are considered the same if their sets of red cells are identical and the numbers written in all cells are identical.

Solve $T$ test cases.

Constraints

Every test case satisfies at least one of Constraint 1 and Constraint 2.

Constraint 1

  • $1 \leq T \leq 10^5$
  • $1 \leq N \leq 10^{18}$
  • $0 \leq K \leq \min(2 \times N, 10^5)$
Constraint 2

  • $1 \leq T \leq 5$
  • $1 \leq N \leq 10^{18}$
  • $0 \leq K \leq \min(2 \times N, 10^{18})$

Input

The input is given in the following format, where $N_i, K_i$ are the values of $N,K$ in the $i$-th test case. 
$T$
$N_1$ $K_1$
$\vdots$
$N_T$ $K_T$

Output

Output $T$ lines. The $i$-th line should contain the answer to the $i$-th test case. (The last line must also end with a newline.)

Sample

Sample 1
Input
15
1 0
1 1
1 2
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
3 5
3 6
Output
1
2
1
1
4
10
12
6
1
6
27
84
162
180
90

This test case satisfies Constraint 1.
For example, when $(N, K) = (2, 2)$, the following $10$ states satisfy the conditions.

Sample 2
Input
3
12345 6789
20221218 100000
1000000000000000000 987654321
Output
200042644
306869647
629032458

This test case satisfies Constraint 2.

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