TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6430
  • 問題
  • P6430「THUPC 2017」小 L 的计算题 / Sum
    制限 : 時間制限 : 9000 MS   メモリ制限 : 565536 KB
    審判説明 : 9s,512m
    問題説明

    现有一个长度为 \(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\)

    入力形式

    输入包含多组数据。

    输入的第一行包含一个整数 \(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}\)

    ヒント

    样例输入

    2
    3
    2 3 3
    5
    1 2 3 4 5
    

    样例输出

    32
    4675