#2022. 生成树
生成树
题目背景
我们是未成熟的斗士 现在绝不认输
我们是未成熟的梦想家 现在绝不哭泣
题目描述
现给定一个无向完全图 和一个长度为 的权值数组 . 表示编号为 的节点的权值.
定义一条边 的边值为 ,满足 ,也就是边连接的两个节点的权值的异或和;定义 的一个生成树 的权值为 ,满足 ,也就是树上边的边权和.
您需要求出 .即 中所有不同生成树的权值的和.
我们认为两棵生成树是不同的,当且仅当两棵树的边集 不完全相同,即至少存在一条边,满足其仅属于两棵生成树中的其中一棵.
输入格式
包括两行.
第一行是一个整数 ,表示 ,即节点个数.
第二行是 个整数,依次为 .
输出格式
一行一个整数.表示你的答案对 取模.
样例 #1
样例输入 #1
3
1 2 3
样例输出 #1
12
样例 #2
样例输入 #2
6
1 1 4 5 1 4
样例输出 #2
19008
样例 #3
样例输入 #3
10
1 1 4 5 1 4 1 9 1 9
样例输出 #3
567022588
提示
样例 #1 说明:
考虑一共存在三个生成树 .
它们的权值分别为 $(1\oplus 2)+(2\oplus 3)=4,(1\oplus 3)+(3\oplus 2)=3,(3\oplus 1)+(1\oplus 2)=5$.
有 .
数据点约束
保证对于所有数据,,.
测试点编号 | 数据范围 | 特殊性质 |
---|---|---|
所有 相等 | ||