When and where do they leave the bridge?

After Action \(2\) is completed, suppose there are \(l\) servals facing left: the \(X_{1}\)-th, \(X_{2}\)-th, \(\cdots\), \(X_{l}\)-th servals from left to right. Also, suppose there are \(r\) servals facing right: the \(Y_{1}\)-th, \(Y_{2}\)-th, \(\cdots\), \(Y_{r}\)-th servals from left to right.

For the \(i\)-th serval, the following holds:

• If \(i \leq l\), the \(i\)-th serval will reach the left end, and the time it can stay on the bridge is \(A_{X_{i}}\).
• If \(l < i\), the \(i\)-th serval will reach the right end, and the time it can stay on the bridge is \(L - A_{Y_{N-i}}\).

This holds because the relative positions of the servals do not change, and even if the servals pass each other instead of reversing direction upon collision, the set of positions of the servals does not change.

Optimal direction to face

Given the above properties, what should the \(i\)-th serval do in Action \(2\)? Suppose that, just after Action \(1\), there are \(l'\) servals facing left and \(r'\) servals facing right.

If \(i \leq l'\)

The \(i\)-th serval is guaranteed to reach the left end.

Therefore, it can stay on the bridge for a time corresponding to the distance from the left end to the \(i\)-th serval among those facing left. If it faces left, its position among the servals facing left will be further left. Hence, it is optimal to face right.

If \(N+1-i \leq r'\)

The \(i\)-th serval is guaranteed to reach the right end.

Similar to the case when \(i \leq l'\), it is optimal to face left.

If \(l' = i - 1\) and \(r' = N - i\)

Suppose the rightmost serval facing left after Action \(1\) is the \(a\)-th serval, and the leftmost serval facing right is the \(b\)-th serval.

• When \(a = i - 1\)

If \(A_{i} < L - A_{i}\), it is optimal to face right; otherwise, it is optimal to face left.

• When \(i + 1 \leq a\)

If \(A_{a} < L - A_{b}\), it is optimal to face right; otherwise, it is optimal to face left.

Considering contributions

Now that we know the optimal direction for the \(i\)-th serval to face, let’s consider the contributions to solve this problem efficiently.

When \(i \leq l'\) and the time \(i\) reaches the left end is \(A_{j}\)

This occurs when the \(j\)-th serval is facing left, and among the \(j - 2\) servals to the left of the \(j\)-th serval other than the \(i\)-th serval, exactly \(i - 1\) are facing left. Therefore, the number of such combinations is \(\left( \begin{matrix} j - 2\\ i - 1\\ \end{matrix} \right)2 ^ {N - j}\).

The value obtained by multiplying this by \(A_{j}\) can be transformed as follows:

\[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)!}\]

Since this can be decomposed into the product of expressions for \(i\), \(j\), and \(j - i\), the contribution to the answer for all \((i, j)\) pairs can be obtained in \(O(N\log(N))\) time using convolution.

When \(N+1-i \leq r'\) and the time \(i\) reaches the right end is \(L - A_{j}\)

This case can be handled in the same way as above by reversing the direction.

When \(l' = i - 1\) and \(r' = N - i\) and the time to reach the left end is \(A_{j}\)

First, consider the case when \(j \neq i\).

The rightmost serval facing left after Action \(1\) must be the \(j\)-th serval.

When the leftmost serval facing right is the \(k\)-th serval, \(L - A_{k} \leq A_{j}\) must hold.

Let \(b\) be the smallest integer satisfying \(L - A_{b} \leq A_{i}\). Then, the \(1\)-st, \(2\)-nd, \(\dots\), \((b - 1)\)-th servals must face left. Also, the \((j + 1)\)-th, \((j + 2)\)-th, \(\dots\), \(N\)-th servals must face right, and the \(j\)-th serval must face left. Therefore, \(b + 1 \leq i < j\).

Among the \(b\)-th, \((b + 1)\)-th, \(\dots\), \((j - 1)\)-th servals that are remaining, exactly \(i - b - 1\) of the \(j - b - 1\) servals other than the \(i\)-th serval must face left. Therefore, \(A_{j}\left( \begin{matrix} j - b - 1\\ i - b - 1\\ \end{matrix} \right)\).

When \(i = j\), this case occurs only if the \(1\)-st, \(2\)-nd, \(\dots\), \((i - 1)\)-th servals face left, the \((i + 1)\)-th, \((i + 2)\)-th, \(\dots\), \(N\)-th servals face right, and \(L - A_{i} \leq A_{i}\) holds. Thus, the contribution of \(j\) to \(i\) is \(A_{i}\).

Here, if \(f(x)\) is a polynomial such that \([x^{i}]f(x)\) is the answer for \(i\), the contribution of \(j\) to \(f(x)\) is \(A_{j}x^{b+1}(1+x)^{j-b-1}\). However, if there exists a \(j\) such that \(j = b\), the contribution of \(j\) to \(f(x)\) is \(A_{j}x^{j}\).

Therefore, if \(c\) is the smallest integer satisfying \(L \leq 2A_{i}\), and \(B_{i}\) is the smallest integer satisfying \(L - A_{b} \leq A_{i}\), the total contribution of all \(j\) to \(f(x)\) can be obtained by evaluating the following polynomial:

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

Since \(B_{i}\) is monotonically decreasing with respect to \(i\), and \(i - B_{i}\) is monotonically increasing with respect to \(i\), this expression can be evaluated in \(O(N (\log{N})^{2})\) using divide-and-conquer and convolution.

When \(l' = i - 1\) and \(r' = N - i\) and the time to reach the right end is \(L - A_{j}\)

This can be obtained in the same way as above by reversing the direction, but note that some inequalities will no longer be strict. Also, there is an implementation strategy to calculate the state where \(l' = i - 1\) and \(r' = N - i\) together.

By calculating all of the above and summing them up, the answer can be obtained. The time complexity is \(O(N(\log{N})^{2})\).

C++ Implementation Example

Python Implementation Example

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)