橋からいなくなる時間と場所

行動 \(2\) まで終わった時点で、左を向いているサーバルが \(l\) 匹で、左から順に、\(X_{1}\) 匹目、\(X_{2}\) 匹目、\(\cdots\) 、\(X_{l}\) 匹目のサーバルが左を向いているとします。また、右を向いているサーバルが \(r\) 匹で、左から順に、\(Y_{1}\) 匹目、\(Y_{2}\) 匹目、\(\cdots\) 、\(Y_{r}\) 匹目であるとします。

\(i\) 匹目のサーバルについて、以下が成り立ちます。

• \(i\leq l\) ならば、\(i\) 匹目のサーバルは左端に辿り着き、橋の上にいられる時間は \(A_{X_{i}}\)
• \(l < i\) ならば、 \(i\) 匹目のサーバルは右端に辿り着き、橋の上にいられる時間は \(L - A_{Y_{N-i}}\)

これは、サーバルの相対的な位置は変わらないことと、サーバルぶつかったときに、反転するのではなくすれ違うとしても、サーバルの位置の集合は変わらないことから成り立ちます。

どちらを向くのが最適か

上記の性質が成り立つことから行動 \(2\) で \(i\) 匹目のサーバルはどのような行動を取れば良いでしょうか。行動 \(1\) が終了した時点で左を向いているサーバルが \(l'\) 匹、右を向いているサーバルが \(r'\) 匹であるとします。

\(i\leq l'\) であるとき

\(i\) 匹目のサーバルは左に辿り着くことが確定しています。

よって、左を向いているサーバルのうち左から \(i\) 匹目のサーバルと左端の距離に応じた時間だけ橋の上にいられます。もし左を向くと左を向いているサーバルのうち左から \(i\) 匹目のサーバル位置はより左になります。よって、右を向くのが最適です。

\(N+1-i\leq r'\) であるとき

\(i\) 匹目のサーバルは右に辿り着くことが確定しています。

\(i\leq l'\) のときと同様の考えで左を向くのが最適です。

\(l' = i - 1 \) かつ \(r' = N - i\) であるとき

行動 \(1\) 後に左を向いているサーバルのうち一番右にいるサーバルが \(a\) 匹目のサーバルであり、右を向いているサーバルのうち一番左にいるサーバルが \(b\) 匹目のサーバルであるとします。

• \(a = i - 1\) のとき

\(A_{i}<L-A{i}\) なら右を向く、そうでないなら左を向くのが最適です。

• \(i + 1 \leq a\) のとき

\(A_{a}<L-A_{b}\) なら右を向く、そうでないなら左を向くのが最適です。

寄与を考える

以上で \(i\) 匹目のサーバルが向くべき方がわかりました。この問題を高速に解くために次に寄与を考えます。

\(i\leq l'\) かつ \(i\) が左に辿り着く時間が \(A_{j}\) であるとき

\(j\) 匹目のサーバルが左を向いていて、\(j\) 匹目のサーバルより左にいる \(i\) 匹目以外の \(j - 2\) 匹のサーバルのうち、ちょうど \(i - 1\) 匹が左を向いているときであるため、そのような向いている方の組み合わせは \(\left( \begin{matrix} j - 2\\ i - 1\\ \end{matrix} \right)2 ^ {N - j}\) となります。

この値に \(A_{j}\) をかけた値は以下のように変形できます。

\[A_{j}\left( \begin{matrix} j - 2\\ i - 1\\ \end{matrix} \right)2 ^ {N - j} = A_{j}(j - 2)!2^{N-j}\times \frac{1}{(i - 1)!}\times \frac{1}{(j-i-1)!}\]

\(i\) の式と \(j\) の式と\(j - i\) の式の積に分解できるので、畳み込みを用いることで全ての \((i, j)\) の組に対する \(i\) への答えの寄与は時間計算量 \(O(N\log(N))\) で求められます。

\(N+1-i\leq r'\) かつ \(i\) が右に辿り着く時間が \(L - A_{j}\) であるとき

反転して上記と同じ方法で求めれば良いです。

\(l' = i - 1 \) かつ \(r' = N - i\) かつ左に時間 \(A_{j}\) で辿り着くとき

まず、\(j\neq i\) のときを考えます。

行動 \(1\) 後に左を向いているサーバルのうち一番右にいるサーバルが \(j\) 匹目のサーバルである必要があります。

右を向いているサーバルのうち、一番左にいるサーバルが \(k\) 匹目のサーバルであるとき、\(L - A_{k} \leq A_{j}\) である必要があります。

\(b\) を \(L-A_{b}\leq A_{i}\) を満たす最小の整数 \(b\) とすると、左から \(1,2,\dots b - 1\) 匹目のサーバルは左を向いている必要があります。また、\(j+1,j+2,\dots N\) 匹目のサーバルは右を \(j\) 匹目のサーバルは左を向いている必要があります。よって、\(b + 1\leq i < j\) となります。

残りの \(b, b + 1, \dots j - 1\) 匹目のサーバルのうち、\(i\) 匹目のサーバルを除く \(j - b - 1\) 匹のサーバルのうち、ちょうど \(i - b - 1\) 匹のサーバルが左を向いている必要があります。よって、\(i\) に対する \(j\) の寄与は \(A_{j}\left( \begin{matrix} j - b - 1\\ i - b - 1\\ \end{matrix} \right)\) となります。

\(i=j\) のとき、\(1,2,\dots,i-1\) 匹目が左を\(i+1,i+2,\dots ,N\) 匹目が右を向いていてかつ \(L-A_{i}\leq A_{i}\) を満たしているときに限ります。よって、 \(j\) の \(i\) に対する寄与は \(A_{j}\) となります。

ここで、\(f(x)\) を \([x^{i}]f(x)\) が \(i\) の答えとなるような多項式とすると、\(j\) の \(f(x)\) に対する寄与は \(A_{j}x^{b+1}(1+x)^{j-b-1}\) となります。ただし、\(j=b\) となるような \(j\) が存在するときがあるので、そのときは \(j\) の \(f(x)\) に対する寄与は \(A_{j}x^{j}\) となります。

よって、\(L\leq 2A_{i}\) を満たす最小の整数 \(i\) を \(c\) とし、\(L-A_{b}\leq A_{i}\) を満たす最小の整数 \(b\) を \(B_{i}\) としたとき、以下の多項式の値が求まれば、全ての \(j\) の \(f(x)\) に対する寄与の総和が求まります。

\[\sum_{i=c}^{N} A_{i}x^{B_{i}+1}(1+x)^{i-B_{i}-1}\]

\(B_{i}\) が \(i\) に対して単調減少かつ、\(i-B_{i}\) が \(i\) に対して単調増加であることから、この式は分割統治と畳み込みを用いて \(O(N (\log{N})^{2})\) で求まります。

\(l' = i - 1 \) かつ \(r' = N - i\) かつ右に時間 \(L-A_{j}\) で辿り着くとき

反転して上記と同じ方法で求めれば良いです。ただし、一部の不等号の等号が外れることに注意してください。なお、\(l' = i - 1 \) かつ \(r' = N - i\) の状態はまとめて計算する実装方針もあります。

以上を全て計算して和を求めれば答えが求まります。時間計算量は \(O(N(\log{N})^{2})\) です。

c++ による実装例

python による実装例

MOD = 998244353

# omit
def convolution(a, b):
    return a * b

# a += b * x ^ c (poly)
def add(a: list[int], b: list[int], c: int) -> None:
    for i in range(len(b)):
        while len(a) <= i + c:
            a.append(0)
        a[i + c] = (a[i + c] + b[i]) % MOD

# input
N, L = map(int,input().split())
A = list(map(int,input().split()))
ans = [0] * N

# Binom
fact = [1] * (N + 1)
fact_inv = [1] * (N + 1)
for i in range(N):
    fact[i + 1] = fact[i] * (i + 1) % MOD
fact_inv[N] = pow(fact[N], -1, MOD)
for i in range(N, 0, -1):
    fact_inv[i - 1] = fact_inv[i] * i % MOD

# (1 + x) ^ a
def make_bin_list(a: int) -> list[int]:
    res = [0] * (a + 1)
    for i in range(a + 1):
        res[i] = fact[a] * fact_inv[a - i] % MOD * fact_inv[i] % MOD
    return res

# pow2
p2 = [1] * (N + 1)
for i in range(N):
    p2[i + 1] = p2[i] * 2 % MOD

# calc
def solve(rev : int) -> list[int]:
    # type 1
    X = [0] * N; Y = [0] * (N + 1)
    for j in range(1, N):
        X[j] = A[j] * fact[j - 1] * p2[N - j - 1] % MOD
        Y[N - j] = fact_inv[j - 1]
        
    res = convolution(X, Y)[N : 2 * N]
    for i in range(N):
        res[i] = res[i] * fact_inv[i] % MOD
    
    # type 2
    B = [0] * 0; C = [0] * 0; D = [0] * 0
    b = N - 1
    for i in range(N):
        if L >= 2 * A[i] + rev:
            continue
        while b != -1 and L - A[b] <= A[i] - rev:
            b -= 1
        if b + 1 < i:
            B.append(b + 2)
            C.append(i - b - 2)
            D.append(A[i])
            res[i] -= A[i]
    
    if len(B) == 0:
        return res
    
    def f(l : int, r : int) -> list[int]:
        if l + 1 == r:
            return [D[l]]
        m = (l + r) // 2
        vr = convolution(f(m, r), make_bin_list(C[m] - C[l]))
        add(vr, f(l, m), B[m - 1] - B[r - 1])
        return vr
    tmp = f(0, len(B))
    add(res, convolution(tmp, make_bin_list(C[0])), B[-1])
    return res
    
# output
ans1 = solve(0)
A.reverse()
for i in range(N):
    A[i] = L - A[i]
ans2 = solve(1)
A.reverse()
for i in range(N):
    print((ans1[i] + ans2[N - i - 1] + max(A[i], L- A[i])) % MOD)