{"problem":{"name":"[蓝桥杯 2024 国 A] 异或路径","description":{"content":"给定一棵有 $n$ 个结点的树，结点 $1$ 至 $n$ 编号。编号为 $x > 1$ 的结点与编号为 $\\lfloor \\sqrt x \\rfloor$  的结点有一条权值为 $x-\\lfloor \\sqrt x \\rfloor ^ 2$ 的边。   定义一条路径的价值为这条路径上的所有边的权值的异或和。如果两条路径包含不同的边，则认为这两条路径不同。求这棵树的所有本质不同的简单路的价值的乘积（","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":"LGP10583"},"statements":[{"statement_type":"Markdown","content":"给定一棵有 $n$ 个结点的树，结点 $1$ 至 $n$ 编号。编号为 $x > 1$ 的结点与编号为 $\\lfloor \\sqrt x \\rfloor$\n 的结点有一条权值为 $x-\\lfloor \\sqrt x \\rfloor ^ 2$ 的边。\n \n定义一条路径的价值为这条路径上的所有边的权值的异或和。如果两条路径包含不同的边，则认为这两条路径不同。求这棵树的所有本质不同的简单路的价值的乘积（价值为 $0$ 的除外），答案对 $998\\ 244\\ 353$ 取模。\n\n## Input\n\n输入一行包含一个整数 $n$。\n\n## Output\n\n输出一行包含一个整数表示答案。\n\n[samples]\n\n## Note\n\n对于 $40\\%$ 的评测用例，$n\\le 10^3$；  \n对于 $70\\%$ 的评测用例，$n\\le 10^6$；  \n对于所有评测用例，$1\\le n\\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10583","tags":["2024","分块","字典树 Trie","快速沃尔什变换 FWT","蓝桥杯国赛","根号分治"],"sample_group":[["5","36"]],"created_at":"2026-03-03 11:09:25"}}