蓝桥杯2024年第十五届决赛真题-异或路径

给定一棵有 n 个结点的树，结点 1 至 n 编号。编号为 x > 1 的结点与编号为 ⌊√x⌋ 的结点有一条权值为 x − ⌊ √x⌋² 的边。

定义一条路径的价值为这条路径上的所有边的权值的异或和。如果两条路径包含不同的边，则认为这两条路径不同。求这棵树的所有本质不同的简单路的价值的乘积（价值为 0 的除外），答案对 998244353 取模。

输入一行包含一个整数 n 。

输出一行包含一个整数表示答案。

5

36

【评测用例规模与约定】

对于 40% 的评测用例，n ≤ 10³ ；

对于 70% 的评测用例，n ≤ 10⁶ ；

对于所有评测用例，1 ≤ n ≤ 10⁹ 。