A6097. 「THUPC 2017」小 L 的计算题 / Sum
编程题
省选/NOI-
知识点
题目描述
现有一个长度为 $n$ $(1 \le n\le 2\times 10^5)$ 的非负整数数组 $\{a_i\}$。小 L 定义了一种神奇变换：
$$ f_k=\sum_{i=1}^{n}a_i^k\pmod{ 998244353 } $$
小 L 计划用变换生成的序列 $f$ 做一些有趣的事情，但是他并不擅长算乘法，所以来找你帮忙，希望你能帮他尽快计算出 $f_1\sim f_n$。
$$ f_k=\sum_{i=1}^{n}a_i^k\pmod{ 998244353 } $$
小 L 计划用变换生成的序列 $f$ 做一些有趣的事情，但是他并不擅长算乘法，所以来找你帮忙，希望你能帮他尽快计算出 $f_1\sim f_n$。
输入格式
输入包含多组数据。
输入的第一行包含一个整数 $T$ $(1\le T\le 20)$, 表示数据组数。
接下来 $2T$ 行，每两行代表一组测试数据。
每组数据的第一行包含一个整数 $n$，表示数组 $\{a_i\}$ 的长度。接下来一行 $n$ 个整数，描述数组 $\{a_i\}$。
保证输入的 $a_i$ 满足 $0\le a_i\le 10^9$。在一个测试文件中，保证有 $\sum n\le 4\times 10^5$。
输入的第一行包含一个整数 $T$ $(1\le T\le 20)$, 表示数据组数。
接下来 $2T$ 行，每两行代表一组测试数据。
每组数据的第一行包含一个整数 $n$，表示数组 $\{a_i\}$ 的长度。接下来一行 $n$ 个整数，描述数组 $\{a_i\}$。
保证输入的 $a_i$ 满足 $0\le a_i\le 10^9$。在一个测试文件中，保证有 $\sum n\le 4\times 10^5$。
输出格式
我们不想让你输出过多的数。因此，令 $\text{ans}=f_1\oplus f_2\oplus\dots\oplus f_n$，其中 $\oplus$ 表示**异或**操作，在 C++ / Java / Python 中，它可以表示为
对每组数据，你需要输出一行一个整数，表示 $\text{ans}$。
^。对每组数据，你需要输出一行一个整数，表示 $\text{ans}$。
输入输出样例
输入 #1
2 3 2 3 3 5 1 2 3 4 5
输出 #1
32 4675