生成树

Luogu
IDLGP9619
Time1000ms
Memory128MB
DifficultyP4
数学生成树Prüfer 序列
现给定一个无向完全图 $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$ 不完全相同,即至少存在一条边,满足其仅属于两棵生成树中的其中一棵. ## Input 包括两行. 第一行是一个整数 $n$,表示 $|V|$,即节点个数. 第二行是 $n$ 个整数,依次为 $a_1\sim a_n$. ## Output 一行一个整数.表示你的答案对 $998244353$ 取模. [samples] ## Background > 我们是未成熟的斗士 现在绝不认输 > > 我们是未成熟的梦想家 现在绝不哭泣 ## Note ### 样例 #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$|||
Samples
Input #1
3
1 2 3
Output #1
12
Input #2
6
1 1 4 5 1 4
Output #2
19008
Input #3
10
1 1 4 5 1 4 1 9 1 9
Output #3
567022588
API Response (JSON)
{
  "problem": {
    "name": "生成树",
    "description": {
      "content": "现给定一个无向完全图 $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\\",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9619"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "现给定一个无向完全图 $G(V,E)$ 和一个长度为 $|V|$ 的权值数组 $a$.$a_i$ 表示编号为 $i$ 的节点的权值.\n\n定义一条边 $e(u,v)$ 的边值为 $val(e)$,满足 $val(e)=a_u\\oplus a_v$,也就是边连接的两个节点的权值的异或和;定义 $G$ 的一个生成树 $T(V,E_t)$ 的权值为 $Val(T)$,满足 $Val(T)=\\sum_{e\\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments