P9162 variance

Given a sequence $a_1,a_2,\cdots,a_n$, define $f(l,r)=(a_l\oplus a_{l+1}\oplus \cdots \oplus a_r)+(a_l\vee a_{l+1}\vee \cdots \vee a_r)$, where $\oplus$ denotes the **bitwise XOR** operation, and $\vee$ denotes the **bitwise OR** operation. You need to compute the variance $v$ of all values $f(l,r)$ that satisfy $1\le l \le r \le n$. To avoid precision errors, and since the answer may be very large, output $(v\times \frac{n^2\times (n+1)^2}{4}) \kern{3pt}\mathrm {mod}\kern{3pt} 998244353$. **Note: Do not take modulo during the computation. Only take modulo for the final result.**

The first line contains a positive integer $n$. The second line contains $n$ positive integers $a_1,a_2,\cdots,a_n$.

Output an integer $(v\times \frac{n^2\times (n+1)^2}{4}) \kern{3pt}\mathrm {mod}\kern{3pt} 998244353$.

Definition of variance: for $n$ numbers $a_1,a_2,\cdots,a_n$, their variance is: $$ \frac 1 n\sum_{i=1}^n (a_i-\bar{a})^2 $$ where $\bar{a}$ is the average of $a_1,a_2,\cdots,a_n$, that is, $\dfrac {1} {n} \displaystyle\sum\limits_{i=1}^n a_i$. ---- For $10\%$ of the testdata, $n \le 50$. For $30\%$ of the testdata, $n \le 5000$. For another $20\%$ of the testdata, $a_i \le 100$. For $100\%$ of the testdata, $1\le n\le 10^5,1\le a_i < 2^{31}$. Translated by ChatGPT 5