Random Walk on a Binary Sequence with Bit‐Flips

A point is located on a binary sequence (each character is either 0 or 1) of length \(n\). Initially the point is at position \(p\) (1-indexed). The following process is repeated:

• If the entire sequence consists of the same character, the process stops.
• Otherwise, let the current position be \(p\). Choose a position \(q\) uniformly at random from \(1,2,\dots,n\). Move the point to \(q\), then flip the bit at position \(q\) (i.e. 0 becomes 1 and 1 becomes 0). The total cost increases by \(f(|p-q|)\) where \[ f(x)= A x^2 + B x, \] and \(A\) and \(B\) are given constants (the distance \(|p-q|\) is taken in the absolute value).

You will then perform \(q\) modifications. Each modification permanently flips the bit at a given index in the sequence and then asks for the following: if the process were started with initial point \(p\) (given in the query) on the current sequence, what is the expected total cost (modulo \(998244353\)) to finish the process?

The answer to each query is defined as follows. When the process starts from a non‐absorbing configuration (that is, the binary sequence is not all 0’s or all 1’s) the process makes one move from the given starting position \(p\). In this move the expected cost incurred is

[ C(p)= \frac1{n} \sum_{q=1}^{n} f(|p-q|)]

After the move the point lands at a uniformly random position. Let (C_{avg}\nobreak= \frac1{n} \sum_{p=1}^{n} C(p)) be the average cost per move if the point is uniformly distributed. Moreover, if the current configuration has exactly (x) ones (and hence (n-x) zeros), then the process will take an expected (T(x)) steps (moves) before termination. (It can be shown that, regardless of the moves, the number of steps depends only on (x); when (x=0) or (x=n) the process terminates immediately.)

Thus for a non‐absorbing configuration a query with starting point \(p\) should output the value

[ \text{Answer} = C(p) + (T(x)-1) \cdot C_{avg} \pmod{998244353}, ]

where \(x\) is the number of ones in the current sequence. (If the sequence is absorbing the answer is defined to be 0.)

Random input generation:

// A random generator is provided
struct Random {
  unsigned long long X;
  void init(unsigned long long seed) { X = seed; }
  unsigned long long Rand() {
    X ^= X <> 7;
    X ^= X <
// The initial binary sequence is generated using seed1:
R.init(seed1);
for (int i = 1; i <= n; i++) seq[i] = R.Rand() & 1;
// For each query, using seed2:
R.init(seed2);
for (int i = 1; i <= q; i++){
idx = R.Rand() % n + 1;  // position to flip permanently
p = R.Rand() % n + 1;    // starting point for query
ans ^= query(idx, p);
}

</p>

inputFormat

The first line contains six integers: \(n, q, A, B, seed1, seed2\) where \(n\) is the length of the binary sequence, \(q\) is the number of queries, \(A\) and \(B\) are the coefficients in \(f(x)=Ax^2+Bx\), and \(seed1\) and \(seed2\) are the seeds for the random generators.

There is no further input. The binary sequence is generated as described, and the queries are generated using the given seeds.

outputFormat

Output a single integer: the XOR (bitwise exclusive OR) of the answers for all queries. Each answer is the expected cost modulo \(998244353\) (computed as described), and the final output is the XOR of all these values.

sample

5 3 1 2 123 456

3

</p>