[蓝桥杯 2024 国 A] 异或路径

Luogu
IDLGP10583
Time1000ms
Memory512MB
DifficultyP6
2024分块字典树 Trie快速沃尔什变换 FWT蓝桥杯国赛根号分治
给定一棵有 $n$ 个结点的树,结点 $1$ 至 $n$ 编号。编号为 $x > 1$ 的结点与编号为 $\lfloor \sqrt x \rfloor$ 的结点有一条权值为 $x-\lfloor \sqrt x \rfloor ^ 2$ 的边。 定义一条路径的价值为这条路径上的所有边的权值的异或和。如果两条路径包含不同的边,则认为这两条路径不同。求这棵树的所有本质不同的简单路的价值的乘积(价值为 $0$ 的除外),答案对 $998\ 244\ 353$ 取模。 ## Input 输入一行包含一个整数 $n$。 ## Output 输出一行包含一个整数表示答案。 [samples] ## Note 对于 $40\%$ 的评测用例,$n\le 10^3$; 对于 $70\%$ 的评测用例,$n\le 10^6$; 对于所有评测用例,$1\le n\le 10^9$。
Samples
Input #1
5
Output #1
36
API Response (JSON)
{
  "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定义一条路径的价值为这条路径上的所有边的权值的异或和。如果两条路径包含不同的边,则认为这两条路径不同。求这棵树的所有本质不同的简单路的价值的乘积(...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments