{"problem":{"name":"[LSOT-2] Tree and Xor","description":{"content":"给定 $n$，你需要构造一棵 $n$ 个点的以 $1$ 为根的有根树，满足 $\\bigoplus\\limits_{i=1}^ndegree(i)=0$ 且 $fa_2 \\sim fa_n$ 的字典序最小。其中，$\\oplus$ 表示异或运算。 其中 $degree(i)$ 表示与点 $i$ 相连的点数，$fa_i$ 表示点 $i$ 的父节点且 $fa_i < i$。 你需要输出 $\\sum\\l","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10157"},"statements":[{"statement_type":"Markdown","content":"给定 $n$，你需要构造一棵 $n$ 个点的以 $1$ 为根的有根树，满足 $\\bigoplus\\limits_{i=1}^ndegree(i)=0$ 且 $fa_2 \\sim fa_n$ 的字典序最小。其中，$\\oplus$ 表示异或运算。\n\n其中 $degree(i)$ 表示与点 $i$ 相连的点数，$fa_i$ 表示点 $i$ 的父节点且 $fa_i < i$。\n\n你需要输出 $\\sum\\limits_{i=2}^ni \\times fa_i$，若无解则输出 $-1$。\n\n## Input\n\n第一行，一个正整数 $T$，表示询问数量。\n\n接下来每 $T$ 行每行一个正整数 $n$ 表示一次询问。\n\n## Output\n\n一共 $T$ 行，每行一个整数表示答案除 $998244353$ 的余数。\n\n[samples]\n\n## Note\n\n**「本题采用捆绑测试」**\n\n- $\\texttt{Subtask 1(5 pts)：}n \\leq 7$。\n- $\\texttt{Subtask 2(10 pts)：} n \\leq 20$。\n- $\\texttt{Subtask 3(20 pts)：}\\sum n \\leq 2000$。\n- $\\texttt{Subtask 4(15 pts)：}n = 2^k-1$，其中 $k$ 是自然数。\n- $\\texttt{Subtask 5(50 pts)：}$无特殊限制。\n\n对于所有数据，$1\\le T\\le 10^6$，$2 \\leq n \\leq 10^{9}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10157","tags":["数学","贪心","二分","位运算","Ad-hoc","分类讨论"],"sample_group":[["2\n2\n3","2\n-1"]],"created_at":"2026-03-03 11:09:25"}}