生成树 题目描述 现给定一个无向完全图 G(V,E) 和一个长度为 ∣V∣ 的权值数组 a．ai 表示编号为 i 的节点的权值． 定义一条边 e(u,v) 的边值为 val(e)，满足 val(e)

生成树l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
题目描述

现给定一个无向完全图 G(V,E) 和一个长度为 ∣V∣ 的权值数组 a．ai 表示编号为 i 的节点的权值．l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

定义一条边 e(u,v) 的边值为 val(e)，满足 val(e)=au⊕av，也就是边连接的两个节点的权值的异或和；定义 G 的一个生成树 T(V,Et) 的权值为 Val(T)，满足 Val(T)=∑e∈Etval(e)，也就是树上边的边权和．l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

您需要求出 ∑TVal(T)．即 G 中所有不同生成树的权值的和．l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

我们认为两棵生成树是不同的，当且仅当两棵树的边集 Et 不完全相同，即至少存在一条边，满足其仅属于两棵生成树中的其中一棵．l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入

l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
包括两行．l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行是一个整数 n，表示 ∣V∣，即节点个数．l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第二行是 n 个整数，依次为 a1∼an．

输出

l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一行一个整数．表示你的答案对 998244353 取模．

样例输入 

3
1 2 3

样例输出 

12

提示

l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例二：l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入：l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
6l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 1 4 5 1 4l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出：l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
19008l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例三：l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入：l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
10l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 1 4 5 1 4 1 9 1 9l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出：l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
567022588l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
l85100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库