Maximum-Cup 2024
コンテスト日時
2024/08/31 (Sa) 14:00 - 16:30

E - Train Sleeper

Benihuki
2
s
1024
MB
100
点

問題文

横一列に $N$ 人の人が並んでいます。左から順に人 $1, ..., N$ と番号を付けます。

まず初めに、各人について、独立にそれぞれ $\dfrac{1}{3}$ の確率で、「左」「中」「右」のどれか 1 つを選びます。

続いて、右の人から順に、以下の操作が行われます。

  • 人 $i+1$ が存在して「左」を選んでいて、かつ人 $i$ がその時点で「中」を選んでいるならば、人 $i$ について「左」に選びなおす。

この操作が行われた後、左の人から順に、以下の操作が行われます。

  • 人 $i-1$ が存在して「右」を選んでいて、かつ人 $i$ がその時点で「中」を選んでいるならば、人 $i$ について「右」に選びなおす。

クエリが $Q$ 個与えられます。
$j$ 番目のクエリでは、上述の一連の操作が終わったとき、人 $i_j$ が「左」「中」「右」を選んでいる確率を、 $\bmod 998244353$ でそれぞれこの順に出力してください。

確率 $\bmod 998244353$ の定義

この問題で求める確率は必ず有理数になることが証明できます。
また、この問題の制約下では、求める確率を既約分数 $\dfrac{y}{x}$ で表したときに $x$ が $998244353$ で割り切れないことが保証されます。

このとき $xz \equiv y \pmod{998244353}$ を満たすような $0$ 以上 $998244353$ 未満の整数 $z$ が一意に定まります。
この $z$ を答えてください。

制約

  • $1 \le N \le 10^{18}$
  • $1 \le Q \le 10^5$
  • $1 \le i_j \le N$
  • 入力はすべて整数である

部分点

この問題はいくつかの小課題に分けられ、その小課題の全てのテストケースに正解した場合に、「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

  1. (15 点) $N \le 12$
  2. (30 点) $N \le 10^5$
  3. (55 点) 追加の制約はない。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$
$i_1$
$i_2$
...
$i_Q$

出力

$Q$ 行出力せよ。
$j (1 \le j \le Q)$ 行目では、人 $i_j$ が最終的に「左」「中」「右」を選んでいる確率 $\bmod 998244353$ をこの順に空白区切りで出力せよ。

入力例 1
2 2 1 2
出力例 1
776412275 887328314 332748118 332748118 887328314 776412275

初期状態として 9 通りあり、それぞれについて以下のように操作が行われます。
なお、「左」「中」「右」をそれぞれ L, M, R で表します。

  • L, L → L, L → L, L
  • L, M → L, M → L, M
  • L, R → L, R → L, R
  • M, L → L, L → L, L
  • M, M → M, M → M, M
  • M, R → M, R → M, R
  • R, L → R, L → R, L
  • R, M → R, M → R, R
  • R, R → R, R → R, R

結果として、

  • 人 1 が「左」「中」「右」を選んでいる確率はそれぞれ $\dfrac{4}{9}, \dfrac{2}{9}, \dfrac{3}{9}$
  • 人 2 が「左」「中」「右」を選んでいる確率はそれぞれ $\dfrac{3}{9}, \dfrac{2}{9}, \dfrac{4}{9}$

となります。

この入力は、小課題 1, 2, 3 の制約を満たします。

入力例 2
10 3 1 5 10
出力例 2
577977209 87519027 332748118 896913651 745543095 354031961 332748118 87519027 577977209

例えば、初期状態が [M, L, R, M, M, R, M, R, L, M] の場合、以下のように操作が行われます。

M, L, R, M, M, R, M, R, L, M  (初期状態)
L, L, R, M, M, R, M, R, L, M  (右の人から操作を行った後)
L, L, R, R, R, R, R, R, L, M  (左の人から操作を行った後)

この入力は、小課題 1, 2, 3 の制約を満たします。

入力例 3
1000000000000000000 5 1 250000000000000000 500000000000000000 750000000000000000 1000000000000000000
出力例 3
686391981 977348608 332748118 354265896 661546408 980676403 72619759 343434787 582189808 99411417 406691929 492141008 332748118 977348608 686391981

この入力は、小課題 3 の制約を満たします。

提出
C++23 (g++ 12.2.0)