Overview

First, we determine the state of Takahashi’s lamp sequence after operations using bit manipulation.
Then, for each split position \(p\), we calculate the sum of “left part value + right part value” and find the maximum.

Analysis

The key point in this problem is that the correspondence of the lamp sequence is the reverse of the usual visual representation.

The \(i\)-th lamp from the left, \(b_i\), corresponds to the \(i\)-th bit from the bottom of the integer.
That is,

• Leftmost lamp = least significant bit
• Rightmost lamp = most significant bit

Takahashi’s Lamp Sequence After Operations

The operation looks at the leftmost lamp.
The leftmost lamp corresponds to the least significant bit of the integer.

• If the least significant bit is \(1\), stop
• If the least significant bit is \(0\), remove it and append \(1\) to the right end

In terms of the integer, this means:

• Discard the lowest bit
• Add a \(1\) to the upper bits

For example, suppose a lamp sequence of length \(N=5\) is

\[ [0, 0, 1, 0, 1] \]

Since the leftmost is the least significant bit, this integer is \(00101\) read from the lower bits.

Operations are performed only while there are consecutive \(0\)s at the left end, so the number of operations is determined by the “number of consecutive \(0\)s at the end of \(X\)”, i.e., trailing zeros.

When \(X \neq 0\), if the number of trailing zeros of \(X\) is \(t\), then the actual number of times the sequence changes is

\[ r = \min(K, t) \]

On the other hand, when \(X=0\), all bits are \(0\), so operations can be performed up to \(N\) times.
Therefore,

\[ r = \min(K, N) \]

If we denote the integer after \(r\) operations as \(tx\), then

\[ tx = (X \gg r) \;|\; ((2^r - 1) \ll (N-r)) \]

Here,

• \(X \gg r\) corresponds to removing \(r\) elements from the left end
• \(((2^r - 1) \ll (N-r))\) corresponds to appending \(r\) ones to the right end

Score at Split Position \(p\)

Let \(z\) be the integer representing a lamp sequence.

When choosing split position \(p\), the left \(p\) elements are the lower \(p\) bits of integer \(z\).
Therefore, the value of the left part is

\[ z \& (2^p - 1) \]

The right part is obtained by shifting right by \(p\) bits.
Since the right part counts again from \(2^0\), its value is

\[ z \gg p \]

Therefore, the contribution of split position \(p\) for lamp sequence \(z\) is

\[ (z \& (2^p - 1)) + (z \gg p) \]

By summing this over Takahashi’s processed lamp sequence and all \(M\) of Aoki’s lamp sequences, we obtain \(A+B\) for that \(p\).

Since \(N \leq 46\), there are at most \(45\) possible split positions.
Even examining \(M+1\) lamp sequences for each \(p\) is fast enough.

Naively simulating the operation \(K\) times would not be feasible since \(K\) can be up to \(10^9\).
However, all we actually need is “how many consecutive \(0\)s are at the beginning,” which can be computed at once using bit operations.

Algorithm

1. Read the input.
2. For Takahashi’s initial state \(X\), determine the actual number of operations \(r\) that cause changes.
   • If \(X=0\), then \(r=\min(K,N)\)
   • Otherwise, let \(t\) be the trailing zeros of \(X\), then \(r=\min(K,t)\)
3. Compute Takahashi’s state after operations, \(tx\).

$\( tx = (X \gg r) \;|\; ((2^r - 1) \ll (N-r)) \)$

1. Add \(tx\) to Aoki’s \(M\) values, considering a total of \(M+1\) lamp sequences.
2. For each split position \(p=1,2,\ldots,N-1\), compute the following.

$\( \sum_z \left((z \& (2^p - 1)) + (z \gg p)\right) \)$

1. Output the maximum value.

Complexity

• Time complexity: \(O(NM)\)
• Space complexity: \(O(M)\)

Implementation Notes

The trailing zeros of \(X\) can be computed in Python as follows:

tz = (X & -X).bit_length() - 1

X & -X extracts only the lowest set bit of \(X\).
If that equals \(2^t\), then the number of trailing zeros is \(t\).

Also, when \(M=0\), the second line of input does not exist, but this can be handled naturally by reading all input at once with sys.stdin.buffer.read().split().

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K, M, X = data[0], data[1], data[2], data[3]

    if X == 0:
        r = K if K < N else N
    else:
        tz = (X & -X).bit_length() - 1
        r = K if K < tz else tz

    tx = (X >> r) | (((1 << r) - 1) << (N - r))

    vals = data[4:4 + M]
    vals.append(tx)

    ans = -1
    for p in range(1, N):
        mask = (1 << p) - 1
        s = 0
        for z in vals:
            s += (z & mask) + (z >> p)
        if s > ans:
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.