题目背景

圣杯在罗斯琳教堂下静待。
大师杰作掩映中相拥入眠。
剑刃圣杯守护着她的门宅。
星空下她可安息无碍。

好的题目不需要花里胡哨的背景。

题目描述

给定一个长度为 $n$ 的数列 $a$，初始情况下 $a_i=i$。

另有一个取值在 $[1,n]$ 内的随机的整数 $x$，它取 $i$ 的概率为 $b_i$。

接下来进行 $k$ 次操作，每次均匀随机地选两个 $[1,n]$ 中的整数 $i,j$（允许 $i=j$），交换 $a_i,a_j$ 的值（如果 $i=j$ 则什么也不干）。问最后 $x$ 在位置 $i$ 上的概率，你需要对所有 $1\leq i\leq n$ 求出答案。你需要输出答案模 $3221225473$ 的值。

我们定义 $x$ 在位置 $i$ 上指 $a_i=x$。

输入格式

一行三个整数 $n,k,seed$。接下来使用如下代码生成 $b_i$：

#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;
}

输出格式

设 $ans_i$ 表示 $x$ 在位置 $i$ 上的概率模 $3221225473$，则输出 $ans_i\times i$ 的异或和。

2 9 998244353

2684354563

7 3 123456789

24313281849

10 9000000000000000000 1000000000000000000

20026214895

4 0 123456789

12357556560

提示

【样例解释】

对于样例 #1：

$b$ 数组为 $\{2134949164 ,1086276310\}$，操作 $9$ 次后 $x$ 在两个位置的概率均为 $\dfrac12$。

对于样例 #2：

$b$ 数组为 $\{1863763622,1043615898,1055155266,1556793106,1763540175,1239801170,1141007183\}$。

【数据范围】

对于 $100\%$ 的数据：

• $2\leq n\leq2\times10^7$，$0\leq k,seed<2^{64}$。
• $1<b_i<3221225473$，$\sum\limits_{i=1}^n b_i\equiv 1\pmod{3221225473}$。
• 数据保证 $1<b_n<3221225473$ 且 $3221225473$ 是质数。

---

本题采用捆绑测试。

$\text{Subtask}$	$n\le$	$k\le$	分值
$0$	$2$	$2^{64}-1$	$1$
$1$	$5$		$4$
$2$	$200$	$200$	$6$
$3$		$2^{64}-1$	$9$
$4$	$2000$		$7$
$5$	$2\times10^7$	$1$	$5$
$6$	$10^6$		$8$
$7$	$2\times10^7$	$10^7$	$10$
$8$	$10^6$	$2^{64}-1$	$15$
$9$	$2\times10^7$		$35$