{"problem":{"name":"[蓝桥杯 2021 国 AB] 异或三角","description":{"content":"给定 $T$ 个数 $n_{1}, n_{2}, \\cdots, n_{T}$, 对每个 $n_{i}$ 请求出有多少组 $a, b, c$ 满足: 1. $1 \\leq a, b, c \\leq n_{i}$; 2. $a \\oplus b \\oplus c=0$ ，其中 $\\oplus$ 表示二进制按位异或; 3. 长度为 $a, b, c$ 的三条边能组成一个三角形。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8766"},"statements":[{"statement_type":"Markdown","content":"给定 $T$ 个数 $n_{1}, n_{2}, \\cdots, n_{T}$, 对每个 $n_{i}$ 请求出有多少组 $a, b, c$ 满足:\n\n1. $1 \\leq a, b, c \\leq n_{i}$;\n\n2. $a \\oplus b \\oplus c=0$ ，其中 $\\oplus$ 表示二进制按位异或;\n\n3. 长度为 $a, b, c$ 的三条边能组成一个三角形。\n\n## Input\n\n输入的第一行包含一个整数 $T$ 。\n\n接下来 $T$ 行每行一个整数, 分别表示 $n_{1}, n_{2}, \\cdots, n_{T}$ 。\n\n## Output\n\n输出 $T$ 行, 每行包含一个整数, 表示对应的答案。\n\n[samples]\n\n## Note\n\n对于 $10 \\%$ 的评测用例, $T=1,1 \\leq n_{i} \\leq 200$; 对于 $20 \\%$ 的评测用例, $T=1,1 \\leq n_{i} \\leq 2000$ ；\n\n对于 $50 \\%$ 的评测用例, $T=1,1 \\leq n_{i} \\leq 2^{20}$;\n\n对于 $60 \\%$ 的评测用例, $1 \\leq T \\leq 100000,1 \\leq n_{i} \\leq 2^{20}$;\n\n对于所有评测用例, $1 \\leq T \\leq 100000,1 \\leq n_{i} \\leq 2^{30}$ 。 \n\n蓝桥杯 2021 国赛 A 组 I 题（B 组 J 题）。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8766","tags":["2021","数位 DP","位运算","蓝桥杯国赛"],"sample_group":[["2\n6\n114514","6\n11223848130"]],"created_at":"2026-03-03 11:09:25"}}