Overview

We determine Takahashi’s sequence after lamp operations (which are performed only while the leftmost bit is \(0\)), then for that sequence and the \(M\) sequences, we calculate the score \(A+B\) for each split position \(p\) and find the maximum.

Analysis

Takahashi’s Sequence After Operations

In the lamp sequence, the leftmost position corresponds to the least significant bit.

If we represent the current state as an integer \(X\), the leftmost lamp is the least significant bit.

• If the leftmost is \(1\), the operation ends.
• If the leftmost is \(0\), that bit is removed and a \(1\) is appended to the right end.

In terms of integers, this operation is:

\[ X \leftarrow (X \gg 1) \;|\; 2^{N-1} \]

However, this operation is only performed while the leftmost bit is \(0\).

In other words, the number of consecutive \(0\)s from the least significant bit of the initial \(X\) is what matters.
Let this be \(z\).

For example, looking from the least significant bit side:

\[ X = \cdots 101000 \]

There are \(3\) consecutive \(0\)s, so \(z=3\).

Since operations are performed at most \(K\) times, the actual number of times the sequence changes is:

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

In the case where \(X=0\), all \(N\) bits are \(0\), so we consider \(z=N\).

The state after \(t\) operations can be obtained by:

• Right-shifting the original \(X\) by \(t\) bits
• Setting the upper \(t\) bits to \(1\) (representing the \(t\) ones appended to the right end)

Therefore, if the value after operations is \(X'\):

\[ X' = (X \gg t) \;|\; \left((2^t-1) \ll (N-t)\right) \]

Score for Each Split Position

Let the state of a lamp sequence be represented as an integer \(S\).

For split position \(p\), the left \(p\) elements are the lower \(p\) bits.
Their value is:

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

On the other hand, the right part consists of bits from position \(p+1\) onward, but within the right part, we count from \(2^0\) again.
As an integer, this is \(S\) right-shifted by \(p\) bits:

\[ S \gg p \]

Therefore, the contribution of this sequence at split position \(p\) is:

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

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

Since \(1 \le p \le N-1\), we simply try all values.

Naively examining each bit every time would be slow, but using bit operations, we can compute each sequence and each \(p\) in \(O(1)\).

Algorithm

1. Find \(z\), the number of consecutive \(0\)s from the least significant bit of \(X\).

   • If \(X=0\), then \(z=N\)
   • Otherwise, it can be found with __builtin_ctzll(X)

2. The actual number of operations that cause changes is:

$\( t = \min(K, z) \)$

1. Compute Takahashi’s sequence after operations, \(finalX\):

$\( finalX = X \gg t \)$

Additionally, if \(t>0\), set the upper \(t\) bits to \(1\).

1. Prepare a total sum[p] for each split position \(p=1,2,\ldots,N-1\).

2. For Takahashi’s sequence \(finalX\), add:

$\( (finalX \& (2^p-1)) + (finalX \gg p) \)$

to sum[p].

1. Similarly, for each \(Y_j\), add its contribution for all \(p\).

2. Finally, the maximum of sum[p] is the answer.

Complexity

• Time complexity: \(O((M+1)N)\)
• Space complexity: \(O(N)\)

Since \(N \le 46\) and \(M \le 2 \times 10^5\), \(O(MN)\) is sufficiently fast.

Implementation Notes

• Since \(N \le 46\), values fit in 64-bit integers.

• Use 1ULL for bit shifts to avoid 32-bit integer overflow from expressions like 1 << p.

• __builtin_ctzll(0) is undefined behavior, so when \(X=0\), branch first and set \(z=N\).

• When \(M=0\), there is no input on the second line, so simply running the reading loop 0 times is fine.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    unsigned long long X;
    cin >> N >> K >> M >> X;

    int z;
    if (X == 0) {
        z = N;
    } else {
        z = min(N, __builtin_ctzll(X));
    }

    int t = (int)min<long long>(K, z);

    unsigned long long finalX = (X >> t);
    if (t > 0) {
        finalX |= ((1ULL << t) - 1ULL) << (N - t);
    }

    vector<unsigned long long> mask(N);
    for (int p = 1; p <= N - 1; p++) {
        mask[p] = (1ULL << p) - 1ULL;
    }

    vector<unsigned long long> sum(N, 0);

    for (int p = 1; p <= N - 1; p++) {
        sum[p] += (finalX & mask[p]) + (finalX >> p);
    }

    for (int i = 0; i < M; i++) {
        unsigned long long Y;
        cin >> Y;
        for (int p = 1; p <= N - 1; p++) {
            sum[p] += (Y & mask[p]) + (Y >> p);
        }
    }

    unsigned long long ans = 0;
    for (int p = 1; p <= N - 1; p++) {
        ans = max(ans, sum[p]);
    }

    cout << ans << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.