生成树(Spanning Trees)

题目描述

现给定一个无向完全图 $G(V,E)$ 和一个长度为 $|V|$ 的权值数组 $a$．$a_i$ 表示编号为 $i$ 的节点的权值．

定义一条边 $e(u,v)$ 的边值为 $val(e)$，满足 $val(e)=a_u\oplus a_v$，也就是边连接的两个节点的权值的异或和；定义 $G$ 的一个生成树 $T(V,E_t)$ 的权值为 $Val(T)$，满足 $Val(T)=\sum_{e\in E_t}val(e)$，也就是树上边的边权和．

您需要求出 $\sum_{T}Val(T)$．即 $G$ 中所有不同生成树的权值的和．

我们认为两棵生成树是不同的，当且仅当两棵树的边集 $E_t$ 不完全相同，即至少存在一条边，满足其仅属于两棵生成树中的其中一棵．

输入格式

包括两行．

第一行是一个整数 $n$，表示 $|V|$，即节点个数．

第二行是 $n$ 个整数，依次为 $a_1\sim a_n$．

输出格式

一行一个整数．表示你的答案对 $998244353$ 取模．

样例输入 #1

3
1 2 3

样例输出 #1

12

样例输入 #2

6
1 1 4 5 1 4

样例输出 #2

19008

样例输入 #3

10
1 1 4 5 1 4 1 9 1 9

样例输出 #3

567022588

数据范围

样例 #1 说明：

考虑一共存在三个生成树 $\{1-2-3\},\{1-3-2\},\{3-1-2\}$．

它们的权值分别为 $(1\oplus 2)+(2\oplus 3)=4,(1\oplus 3)+(3\oplus 2)=3,(3\oplus 1)+(1\oplus 2)=5$．

有 $4+3+5=12$．

数据点约束

保证对于所有数据，$1\le n\le 10^6$，$0\le a_i\le 10^9$． |测试点编号|数据范围|特殊性质| |:-:|:-:|:-:| |$1$||所有 $a_i$ 相等| |$2\sim 5$|$n\le 4$|| |$6\sim 10$|$n\le 300$|| |$11\sim 12$|$n\le 5\times 10^4$|$a_i=[i=1]$| |$11\sim 15$|$n\le 5\times 10^4$|| |$16\sim 20$|||

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1750。

测试点分布

出处：原题链接