P7431 [THUPC 2017] 小 L 的计算题

现有一个长度为 $n$ 的非负整数数组 $\{a_i\}$ 。小 L 定义了一种神奇变换： $$f_k=\left(\sum_{i=1}^na_i^k\right)\bmod 998244353$$ 小 L 计划用变换生成的序列 $f$ 做一些有趣的事情，但是他并不擅长算乘法，所以来找你帮忙，希望你能帮他尽快计算出 $f_{1\dots n}$。

输入包含多组数据。 输入的第一行包含一个整数 $T$ , 表示数据组数。 接下来 $2T$ 行，每两行代表一组测试数据。 每组数据的第一行包含一个整数 $n$，表示数组 $\{a_i\}$ 的长度。接下来一行 $n$ 个整数，描述数组 $\{a_i\}$。 保证输入的 $a_i$ 满足 $0\le a_i\le10^9$。在一个测试文件中，保证有 $\sum n\le 4\times 10^5$。

我们不想让你输出过多的数。因此，令 $ans=\bigoplus_{i=1}^{n}f_i$，其中 $\bigoplus$ 表示**异或**操作，在 C++ / Java / Python 中，它可以表示为 `^`。 对每组数据，你需要输出一行一个整数，表示 $ans$。

对于 $100\%$ 的数据，$0\le a_i\le10^9$，$1\le n\le 2\times 10^5$，$\sum n\le 4\times 10^5$。 #### 版权信息 来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。