{"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\\in E_t}val(e)$，也就是树上边的边权和．\n\n您需要求出 $\\sum_{T}Val(T)$．即 $G$ 中所有不同生成树的权值的和．\n\n我们认为两棵生成树是不同的，当且仅当两棵树的边集 $E_t$ 不完全相同，即至少存在一条边，满足其仅属于两棵生成树中的其中一棵．\n\n## Input\n\n包括两行．\n\n第一行是一个整数 $n$，表示 $|V|$，即节点个数．\n\n第二行是 $n$ 个整数，依次为 $a_1\\sim a_n$．\n\n## Output\n\n一行一个整数．表示你的答案对 $998244353$ 取模．\n\n[samples]\n\n## Background\n\n> 我们是未成熟的斗士 现在绝不认输\n>\n> 我们是未成熟的梦想家 现在绝不哭泣\n\n## Note\n\n### 样例 #1 说明：\n考虑一共存在三个生成树 $\\{1-2-3\\},\\{1-3-2\\},\\{3-1-2\\}$．\n\n它们的权值分别为 $(1\\oplus 2)+(2\\oplus 3)=4,(1\\oplus 3)+(3\\oplus 2)=3,(3\\oplus 1)+(1\\oplus 2)=5$．\n\n有 $4+3+5=12$．\n\n### 数据点约束\n保证对于所有数据，$1\\le n\\le 10^6$，$0\\le a_i\\le 10^9$．\n|测试点编号|数据范围|特殊性质|\n|:-:|:-:|:-:|\n|$1$||所有 $a_i$ 相等|\n|$2\\sim 5$|$n\\le 4$||\n|$6\\sim 10$|$n\\le 300$||\n|$11\\sim 12$|$n\\le 5\\times 10^4$|$a_i=[i=1]$|\n|$11\\sim 15$|$n\\le 5\\times 10^4$||\n|$16\\sim 20$|||","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9619","tags":["数学","生成树","Prüfer 序列"],"sample_group":[["3\n1 2 3","12"],["6\n1 1 4 5 1 4","19008"],["10\n1 1 4 5 1 4 1 9 1 9","567022588"]],"created_at":"2026-03-03 11:09:25"}}