P8944 The Da Vinci Code

> The Holy Grail waits quietly beneath Rosslyn Chapel. > It sleeps embraced in the shadow of a masterwork. > Blade and Grail guard the doorway of her home. > Under the starry sky she may rest in peace. A good problem does not need a fancy background.

Given a sequence $a$ of length $n$, initially $a_i = i$. There is also a random integer $x$ with value in $[1,n]$. The probability that it equals $i$ is $b_i$. Then perform $k$ operations. In each operation, **uniformly at random** choose two integers $i, j$ from $[1,n]$ (allowing $i=j$), and swap the values of $a_i$ and $a_j$ (if $i=j$, do nothing). Ask for the probability that finally $x$ is at position $i$. You need to compute the answer for all $1 \le i \le n$. Output the answers modulo $3221225473$. We say that $x$ is at position $i$ if $a_i = x$.

One line contains three integers $n, k, seed$. Then generate $b_i$ using the following code: ```cpp #include typedef unsigned long long ull; typedef unsigned int uint; typedef long long ll; const uint mod = 3221225473u; const int N = 20000010; ull seed; ull getnext() { seed ^= seed > 17; seed ^= seed

Let $ans_i$ be the probability that $x$ is at position $i$ modulo $3221225473$. Output the XOR-sum of $ans_i \times i$.

#### Sample Explanation For Sample #1: The array $b$ is $\{2134949164, 1086276310\}$. After $9$ operations, the probabilities that $x$ is at the two positions are both $\dfrac12$. For Sample #2: The array $b$ is $\{1863763622, 1043615898, 1055155266, 1556793106, 1763540175, 1239801170, 1141007183\}$. #### Constraints For $100\%$ of the testdata: * $2 \le n \le 2 \times 10^7$, $0 \le k, seed < 2^{64}$. * $1 < b_i < 3221225473$, $\sum\limits_{i=1}^n b_i \equiv 1 \pmod{3221225473}$. * The testdata guarantees $1 < b_n < 3221225473$ and $3221225473$ is prime. --- **This problem uses bundled tests.** | $\text{Subtask}$ | $n \le$ | $k \le$ | Score | |:-:|:-:|:-:|:-:| | $0$ | $2$ | $2^{64}-1$ | $1$ | | $1$ | $5$ | $5$ | $4$ | | $2$ | $200$ | $200$ | $6$ | | $3$ | $200$ | $2^{64}-1$ | $9$ | | $4$ | $2000$ | $2000$ | $7$ | | $5$ | $2 \times 10^7$ | $1$ | $5$ | | $6$ | $10^6$ | $10^6$ | $8$ | | $7$ | $2 \times 10^7$ | $10^7$ | $10$ | | $8$ | $10^6$ | $2^{64}-1$ | $15$ | | $9$ | $2 \times 10^7$ | $2^{64}-1$ | $35$ | Translated by ChatGPT 5