The Da Vinci Code
题目背景
> 圣杯在罗斯琳教堂下静待。
> 大师杰作掩映中相拥入眠。
> 剑刃圣杯守护着她的门宅。
> 星空下她可安息无碍。
好的题目不需要花里胡哨的背景。
题目描述
给定一个长度为 $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$：
```cpp
#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$ 的异或和。
输入输出样例
输入样例 #1
2 9 998244353
输出样例 #1
2684354563
输入样例 #2
7 3 123456789
输出样例 #2
24313281849
输入样例 #3
10 9000000000000000000 1000000000000000000
输出样例 #3
20026214895
输入样例 #4
4 0 123456789
输出样例 #4
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$|$5$|$4$|
|$2$|$200$|$200$|$6$|
|$3$|$200$|$2^{64}-1$|$9$|
|$4$|$2000$|$2000$|$7$|
|$5$|$2\times10^7$|$1$|$5$|
|$6$|$10^6$|$10^6$|$8$|
|$7$|$2\times10^7$|$10^7$|$10$|
|$8$|$10^6$|$2^{64}-1$|$15$|
|$9$|$2\times10^7$|$2^{64}-1$|$35$|