Background

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.

Problem Description

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$.

Input Format

One line contains three integers $n, k, seed$. Then generate $b_i$ using the following code:

#include <cstdio>

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 << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}

uint rd(uint l, uint r) {
	return getnext() % (r - l + 1) + l;
}

int n;
ull k;
uint b[N];

int main() {
	scanf("%d%llu%llu", &n, &k, &seed);
	ull sum = 0;
	for (int i = 1; i < n; ++ i) b[i] = rd(2u, mod - 1), (sum += b[i]) %= mod;
	b[n] = mod + 1 - sum;
}

Output Format

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

2 9 998244353

2684354563

7 3 123456789

24313281849

10 9000000000000000000 1000000000000000000

20026214895

4 0 123456789

12357556560

Hint

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.

Translated by ChatGPT 5