問題一覧 > 通常問題

No.2166 Paint and Fill

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : NyaanNyaanNyaanNyaan / テスター : 👑 NachiaNachia
3 ProblemId : 8867 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-18 16:30:35

注意

この問題は実行時間制限が厳しいので、高速な言語の利用を強く推奨します。
writer 解, tester 解の言語はともに C++ で、実行時間はそれぞれ 3000 ms, 3519 ms です。

ヒント：想定解の計算量(13:30 追記) 想定解の計算量は $X = T + \max(K_i), L = \min(\mathrm{mod}, \max(K_i))$ として $\mathrm{O}(\min(X \log^2 X, T \sqrt{L} \log{L}))$ です。

問題文

縦横 $2 \times N$ のグリッドがあります。グリッドの各マスは白く塗られています。
あなたは次の一連の操作をちょうど 1 回行います。

  • グリッドのマスをちょうど $K$ マス選び、選んだマスを赤く塗り替える。
  • その後、次の条件をすべて満たすようにグリッドの各マスに数を 1 個ずつ書きこむ。
    • $1$ 以上 $N$ 以下の整数すべてがちょうど $2$ 回ずつ登場する。
    • 左から $j$ 列目にある白く塗られたマスには $j$ が書きこまれている。
操作後のグリッドの状態としてあり得るものの個数を $\text{mod }998244353$ で求めてください。
ただし、2 つのグリッドの状態は、赤く塗られたマスの集合、および全てのマスに書きこまれた数が一致しているときに同じ状態であるとみなします。

$T$ 個のテストケースに答えてください。

制約

すべてのテストケースは、制約 1 または制約 2 の少なくとも一方を満たします。

制約 1

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

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

入力

入力は以下の形式で与えられます。ここで $N_i, K_i$ は $i$ 番目のテストケースにおける $N,K$ です。 
$T$
$N_1$ $K_1$
$\vdots$
$N_T$ $K_T$

出力

$T$ 行出力してください。$i$ 行目には $i$ 番目のテストケースへの答えを出力してください。(最終行の末尾も改行してください。)

サンプル

サンプル1
入力
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
出力
1
2
1
1
4
10
12
6
1
6
27
84
162
180
90

このテストケースは制約 1 を満たしています。
例えば $(N, K) = (2, 2)$ の場合は以下の $10$ 通りが条件を満たします。

サンプル2
入力
3
12345 6789
20221218 100000
1000000000000000000 987654321
出力
200042644
306869647
629032458

このテストケースは制約 2 を満たしています。

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