{"raw_statement":[{"iden":"background","content":"> 圣杯在罗斯琳教堂下静待。  \n> 大师杰作掩映中相拥入眠。  \n> 剑刃圣杯守护着她的门宅。  \n> 星空下她可安息无碍。\n\n好的题目不需要花里胡哨的背景。"},{"iden":"statement","content":"给定一个长度为 $n$ 的数列 $a$，初始情况下 $a_i=i$。\n\n另有一个取值在 $[1,n]$ 内的随机的整数 $x$，它取 $i$ 的概率为 $b_i$。\n\n接下来进行 $k$ 次操作，每次**均匀随机**地选两个 $[1,n]$ 中的整数 $i,j$（允许 $i=j$），交换 $a_i,a_j$ 的值（如果 $i=j$ 则什么也不干）。问最后 $x$ 在位置 $i$ 上的概率，你需要对所有 $1\\leq i\\leq n$ 求出答案。你需要输出答案模 $3221225473$ 的值。\n\n我们定义 $x$ 在位置 $i$ 上指 $a_i=x$。"},{"iden":"input","content":"一行三个整数 $n,k,seed$。接下来使用如下代码生成 $b_i$：\n\n```cpp\n#include <cstdio>\n\ntypedef unsigned long long ull;\ntypedef unsigned int uint;\ntypedef long long ll;\n\nconst uint mod = 3221225473u;\nconst int N = 20000010;\n\null seed;\n\null getnext() {\n\tseed ^= seed << 13;\n\tseed ^= seed >> 17;\n\tseed ^= seed << 5;\n\treturn seed;\n}\n\nuint rd(uint l, uint r) {\n\treturn getnext() % (r - l + 1) + l;\n}\n\nint n;\null k;\nuint b[N];\n\nint main() {\n\tscanf(\"%d%llu%llu\", &n, &k, &seed);\n\tull sum = 0;\n\tfor (int i = 1; i < n; ++ i) b[i] = rd(2u, mod - 1), (sum += b[i]) %= mod;\n\tb[n] = mod + 1 - sum;\n}\n```\n"},{"iden":"output","content":"设 $ans_i$ 表示 $x$ 在位置 $i$ 上的概率模 $3221225473$，则输出 $ans_i\\times i$ 的异或和。"},{"iden":"note","content":"#### 【样例解释】\n\n对于样例 #1：\n\n$b$ 数组为 $\\{2134949164 ,1086276310\\}$，操作 $9$ 次后 $x$ 在两个位置的概率均为 $\\dfrac12$。\n\n对于样例 #2：\n\n$b$ 数组为 $\\{1863763622,1043615898,1055155266,1556793106,1763540175,1239801170,1141007183\\}$。\n\n#### 【数据范围】\n对于 $100\\%$ 的数据：\n\n* $2\\leq n\\leq2\\times10^7$，$0\\leq k,seed<2^{64}$。\n* $1<b_i<3221225473$，$\\sum\\limits_{i=1}^n b_i\\equiv 1\\pmod{3221225473}$。\n* 数据保证 $1<b_n<3221225473$ 且 $3221225473$ 是质数。\n\n---\n\n**本题采用捆绑测试**。\n\n| $\\text{Subtask}$ |$n\\le$|$k\\le$|分值|\n|:-:|:-:|:-:|:-:|\n|$0$|$2$|$2^{64}-1$|$1$|\n|$1$|$5$|$5$|$4$|\n|$2$|$200$|$200$|$6$|\n|$3$|$200$|$2^{64}-1$|$9$|\n|$4$|$2000$|$2000$|$7$|\n|$5$|$2\\times10^7$|$1$|$5$|\n|$6$|$10^6$|$10^6$|$8$|\n|$7$|$2\\times10^7$|$10^7$|$10$|\n|$8$|$10^6$|$2^{64}-1$|$15$|\n|$9$|$2\\times10^7$|$2^{64}-1$|$35$|"}],"translated_statement":null,"sample_group":[["2 9 998244353\n","2684354563\n"],["7 3 123456789\n","24313281849\n"],["10 9000000000000000000 1000000000000000000\n","20026214895\n"],["4 0 123456789\n","12357556560\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}