公式解説で Bonus として言及されている人が \(n\) 人いる場合の解法です。

解法

公式解説で述べられている通り、「初めて」という条件を無視した確率の計算方法が分かればよいです。以降は「初めて」という条件を無視した確率の計算を考えます。

時刻 \(t\) における人 \(i\) の人 \(1\) からの相対座標を \(2\) で割った値を \(a ^ t _ i\) とします。\(T \lt a ^ 0 _ n\) の場合の答えは明らかに \(0\) です。また、人を入れ替えても求める確率は変わらないので、 一般性を失わず \(0 = a ^ 0 _ 1 \leq a ^ 0 _ 2 \leq \cdots \leq a ^ 0 _ n\leq T\) を仮定します。初期座標の \(\mathrm{mod}\ 2\) が全て等しいという仮定より \(a ^ t _ i\) は整数です。また \(a\) の定義より必ず \(a ^ t _ 1 = 0\) です。

以降、表記の簡単のため \(a _ i = a _ i ^ 0\) と書きます。

\[\mathsf{dp} _ t\lbrack k _ 2, \ldots, k _ n \rbrack \coloneqq P(a ^ t _ 2 = k _ 2, \ldots, a ^ t _ n = k _ n)\]

と定義します。ここで \(P(\phi)\) は \(\phi\) が起こる確率です。

\(\mathsf{dp} _ t\) から \(\mathsf{dp} _ {t + 1}\) を計算します。人 \(1\) が左右のどちらに進むかで場合分けをします。

1. 人 \(1\) が左に進む場合
   人 \(i\ (\neq 1)\) が左に動いた場合、\(a ^ {t + 1} _ i = a ^ t _ i\) です。一方、人 \(i\ (\neq 1)\) が右に動いた場合、\(a ^ {t + 1} _ i = a ^ t _ i + 1\) です。
2. 人 \(1\) がに右進む場合
   人 \(i\ (\neq 1)\) が左に動いた場合、\(a ^ {t + 1} _ i = a ^ t _ i - 1\) です。一方、人 \(i\ (\neq 1)\) が右に動いた場合、\(a ^ {t + 1} _ i = a ^ t _ i\) です。

従って \(x _ 2, \ldots, x _ n\) を不定元とする多次元の形式的冪級数 \(f _ t\) を

\[f _ t(x _ 2, \ldots, x _ n) \coloneqq \sum _ {k _ 2, \ldots, k _ n} \mathsf{dp} _ t\lbrack k _ 2, \ldots, k _ n \rbrack x _ 2 ^ {k _ 2} \cdots x _ n ^ {k _ n}\]

で定義すると、次が成り立ちます。

\[\begin{aligned}f _ {t + 1} &= \frac{1}{2 ^ n}f _ t \cdot \Biggl(\prod _ {i = 2} ^ n (1 + x _ i) + \prod _ {i = 2} ^ n (1 + x _ i ^ {-1})\Biggr)\\ &= \frac{1}{2 ^ n}f _ t \cdot (1 + x _ 2 ^ {-1} \cdots x _ n ^ {-1})\prod _ {i = 2} ^ n (1 + x _ i)\end{aligned}\]

\(f _ 0 = x _ 2 ^ {a _ 2}\cdots x _ n ^ {a _ n}\) だったので、次が成り立ちます。

\[f _ t = \frac{1}{2 ^ {nt}} x _ 2 ^ {a _ 2}\cdots x _ n ^ {a _ n} (1 + x _ 2 ^ {-1} \cdots x _ n ^ {-1}) ^ t\prod _ {i = 2} ^ n (1 + x _ i) ^ t\]

いま計算したいのは全ての \(t = 0, \ldots, T\) に対する \(f _ t\) の定数項です。二項定理を用いて

\[(1 + x _ 2 ^ {-1} \cdots x _ n ^ {-1}) ^ t = \sum _ {j = 0} ^ t \binom{t}{j} x_ 2 ^ {-j} \cdots x _ n ^ {-j}\]

と展開し、各 \(j = 0, \ldots, t\) に対する

\[g _ {t, j} \coloneqq \frac{1}{2 ^ {nt}}\binom{t}{j}x _ 2 ^ {a _ 2 - j}\cdots x _ n ^ {a _ n - j} \prod _ {i = 2} ^ n (1 + x _ i) ^ t\]

の定数項の総和として \(f _ t\) の定数項を計算することができます。\(g _ {t, j}\) の定数項は次で計算されます。ただし \(\displaystyle \binom{n}{r}\) について \(r\lt 0\) や \(r\gt n\) の場合は \(0\) とします。

\[\frac{1}{2 ^ {nt}}\binom{t}{j} \prod _ {i = 2} ^ n \binom{t}{j - a _ i}.\]

上式を整理すると、\(f _ t\) の定数項は次で表されます。

\[\frac{(t!) ^ n}{2 ^ {nt}} \sum _ {j = a _ n} ^ t \frac{1}{\prod _ {i = 1} ^ n(j - a _ i)!}\cdot \frac{1}{\prod _ {i = 1} ^ n(t - j + a _ i)!}.\]

ここで、仮定と制約より \(a _ n \leq j \leq t \leq T\) のもとで \(0\leq j - a _ i \lt P\ (=998144353)\) および \(0\leq t - j + a _ i \lt P\) が成り立っており、 \(\displaystyle \prod _ {i = 1} ^ n(j - a _ i)! \neq 0\) および \(\displaystyle \prod _ {i = 1} ^ n(t - j + a _ i)!\neq 0\) であるから乗法逆元は必ず存在することに注意します。

\(\displaystyle p(j)\coloneqq \prod _ {i = 1} ^ n(j - a _ i)!, q(j) \coloneqq \prod _ {i = 1} ^ n(j + a _ i)!\) と定義すれば、上式は次のように書き直せます。

\[\frac{(t!) ^ n}{2 ^ {nt}} \sum _ {j = a _ n} ^ t \frac{1}{p(j)}\cdot \frac{1}{q(t-j)}.\tag{1}\]

和の部分は畳み込みの形をしているので、\(j = a _ n, \ldots, T\) に対する \(p(j)\) と \(j = 0, \ldots, T - a _ n\) に対する \(q(j)\) が分かっていると仮定すれば全ての \(t = 0, \ldots, T\) に対する \(f _ t\) の定数項を \(O(T\log T)\) 時間で計算できます。

従って、以降の目標は全ての \(j = a _ n, \ldots, T\) に対する \(p(j)\) と全ての \(j = 0, \ldots, T - a _ n\) に対する \(q(j)\) を計算することです。\(p(j)\) の計算は \(q(j)\) の計算とほとんど同様にできるので、ここでは \(q(j)\) の計算方法を説明します。以降、式が煩雑になることを防ぐため \(T' \coloneqq T - a _ n\) とします。

\(j \geq 1\) に関して、次が成り立ちます。

\[q(j) = q(j - 1) \prod _ {i = 1} ^ n (j + a _ i).\]

従って、全ての \(j = 1, \ldots, T'\) に対する \(\displaystyle \prod _ {i = 1} ^ n (j + a _ i)\) の値が計算できれば十分であり、これは多項式 \(\displaystyle f(x) = \prod _ {i = 1} ^ n (x + a _ i)\) の多点評価 (multipoint evaluation) をする問題です。

まず、\(f(x)\) は二分木状に積を計算する分割統治法で \(O(n(\log n) ^ 2)\) 時間で計算できます。そして、多点評価は次のように計算できます。

\(\displaystyle P _ {l, r}(x) \coloneqq \prod _ {j = l} ^ {r - 1} (x - j)\) として、\(f(x)\) を \(P _ {l, r}(x)\) で割った余りを \(R _ {l, r}(x)\) とします。\(f(j) = f(x) \bmod (x - j)\) なので、全ての \(j = 1, \ldots, T\) に対する \(R _ {j, j + 1}(x)\) を計算することが目標です。

\(l\lt m\lt r\) なる \(m\) に対して \(R _ {l, r}(x)\) を \(P _ {l, m}\) で割った余りは \(R _ {l, m}\) と一致し、また \(P _ {m, r}\) で割った余りは \(R _ {m, r}\) と一致します。従って、二分木状にボトムアップに \(P _ {l, r}\) を計算し、トップダウンに \(R _ {l, r}\) を計算する分割統治法で計算することができます。計算の途中で多項式の割り算が登場しますが、これも多項式の次数を \(d\) として \(O(d\log d)\) 時間で可能です。以上より、\(l, r\) に対して例えば \(m = \lfloor (l + r) / 2 \rfloor\) を選ぶことで全体 \(O(T'(\log T') ^ 2 + (n + T')\log (n + T')) = O(T(\log T) ^ 2 + (n + T)\log (n + T))\) 時間で \(f(1), \ldots, f(T')\) を計算できます。

以上で必要な \(p(j), q(j)\) を \(O(T(\log T) ^ 2)\) 時間で計算できました。

\((1)\) の計算では \((t!) ^ n\) の列挙や \(\dfrac{1}{2 ^ {nt}}\) の列挙が必要ですが、例えば繰り返し二乗法で \(O(T\log n)\) 時間で可能です。

問題全体では \(O(n (\log n) ^ 2 + T (\log T) ^ 2)\) 時間となります。

実装: C++ (GCC 9.2.1)