Dotcpp  >  编程题库  >  蓝桥杯2024年第十五届决赛真题-异或路径
题目 3304:

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

时间限制: 2s 内存限制: 512MB 提交: 6 解决: 1

题目描述

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

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

输入格式

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

输出格式

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

样例输入

5

样例输出

36

提示

【评测用例规模与约定】

对于 40% 的评测用例,n ≤ 103

对于 70% 的评测用例,n ≤ 106

对于所有评测用例,1 ≤ n ≤ 109

标签