CF1905E One-X

在这个充满缺陷的悲伤世界里，丑陋的线段树依然存在。 线段树是一种树结构，每个节点代表一个区间，并有其编号。对于一个长度为 $n$ 的数组，可以递归地构建线段树。设函数 $\operatorname{build}(v,l,r)$ 构建以编号为 $v$ 的节点为根、对应区间为 $[l,r]$ 的线段树。 现在定义 $\operatorname{build}(v,l,r)$ 过程如下： - 如果 $l=r$，则节点 $v$ 是叶子节点，停止添加更多的边。 - 否则，添加边 $(v, 2v)$ 和 $(v, 2v+1)$。令 $m=\lfloor \frac{l+r}{2} \rfloor$，然后递归调用 $\operatorname{build}(2v,l,m)$ 和 $\operatorname{build}(2v+1,m+1,r)$。 因此，整个树通过调用 $\operatorname{build}(1,1,n)$ 构建完成。 现在 Ibti 要为一个长度为 $n$ 的数组构建线段树。他想要计算所有叶子节点的非空子集 $S$ 的 $\operatorname{lca}^\dagger(S)$ 之和。注意，非空子集共有 $2^n-1$ 个。由于这个和可能非常大，请输出其对 $998\,244\,353$ 取模的结果。 $^\dagger\operatorname{lca}(S)$ 表示 $S$ 中所有节点的最近公共祖先的编号。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^{18}$），表示要构建线段树的数组长度。

对于每组测试用例，输出一个整数，表示所求的和对 $998\,244\,353$ 取模后的结果。

 对于第一个测试用例： 我们来看所有叶子节点的子集： - $\operatorname{lca}(\{2\})=2$； - $\operatorname{lca}(\{3\})=3$； - $\operatorname{lca}(\{2,3\})=1$。 因此，答案为 $2+3+1=6$。 对于第二个测试用例： 我们来看所有叶子节点的子集： - $\operatorname{lca}(\{4\})=4$； - $\operatorname{lca}(\{5\})=5$； - $\operatorname{lca}(\{3\})=3$； - $\operatorname{lca}(\{4,5\})=2$； - $\operatorname{lca}(\{4,3\})=1$； - $\operatorname{lca}(\{5,3\})=1$； - $\operatorname{lca}(\{4,5,3\})=1$。 因此，答案为 $4+5+3+2+1+1+1=17$。 由 ChatGPT 4.1 翻译