P7953 [✗✓OI R1] Bit Reversal.

myy is traveling in Foshan, Guangdong, so he made a “Gaoming” problem.

A point performs a random walk on a $0/1$ sequence of length $n$. The point’s initial position is $p$. Repeat the following operations: 1. If the entire sequence consists of only one character, stop. 2. Let the point’s current position be $p$. Uniformly at random choose a position $q$, move the point to $q$, flip the character at $q$, and add $f(|p-q|)$ to the total cost, where $f(x)=Ax^2+Bx$, and $A,B$ are two given constants. 3. Go back to step 1. You need to perform $q$ modifications. Specifically, each modification includes: 1. Flip the $0/1$ at position $\mathit{idx}$ in the sequence. 2. Query the expected cost after the process stops, when the initial position is $p$. **Note that once a modification is made, it remains effective.** You need to output the XOR sum of the answers to the $q$ queries, where each answer is the expected cost modulo $998244353$. Since the input and output size is large, the data is generated randomly as follows: ```cpp struct Random { unsigned long long X; void init(unsigned long long seed) { X = seed; } unsigned long long Rand() { X ^= X > 7; X ^= X

One line with six integers $n,q,\mathit{seed1},\mathit{seed2},A,B$. Their meanings are described in “Description”.

One line with one integer $\mathit{ans}$, representing the XOR sum of the $q$ query results, where each expected cost is taken modulo $998244353$.

**[Sample Explanation]** Explanation for sample 1: The three queries are: $110$, $p=3$, answer is $\dfrac{11}{4}$; $010$, $p=3$, answer is $\dfrac{17}{6}$; $110$, $p=1$, answer is $\dfrac{11}{4}$. Modulo $998244353$, they are $249561091$, $831870297$, and $249561091$, and the XOR sum is $831870297$. **[Constraints]** **This problem uses subtask evaluation.** For $100\%$ of the testdata, $3 \leq n \leq 3\times10^6$, $1 \leq q \leq 3\times10^6$, $0 \leq A, B < 998244353$, $\mathit{seed1}, \mathit{seed2}\in [0, 2^{64})$. | Subtask | $n\le$ | $q\le$ | Special Property | Subtask Score | Dependencies | Time Limit | | :----: | :-----: | :-----: | :--------------: | :-----------: | :----------: | :--------: | | 0 | $5$ | $5$ | A | 5 || 1s | | 1 | $50$ | $5$ | / | 18 | Subtask 0 | 1s | | 2 | $600$ | $50$ | / | 12 | Subtask 0~1 | 1s | | 3 | $3000$ | $3000$ | A | 10 | Subtask 0 | 1s | | 4 | $3000$ | $3000$ | / | 10 | Subtask 0~3 | 1s | | 5 | $3\times10^6$ | $3\times10^6$ | / | 45 | Subtask 0~4 | 2s | Special Property A: $A = 0$. > By convention, there should be an interesting postscript here, but since you have already finished the “Ake Monthly Contest”, you probably do not have the patience to read it, so there is none. Translated by ChatGPT 5