{"problem":{"name":"「KDOI-06-S」合并序列","description":{"content":"给定一个长度为 $n$ 的序列 $a_1,a_2,\\ldots a_n$。 你可以对这个序列进行若干（可能为 $0$）次操作。在每次操作中，你将会： * 选择三个正整数 $i<j<k$，满足 $a_i\\oplus a_j\\oplus a_k=0$ 且 $k$ 的值不超过此时序列的长度。记 $s=a_i\\oplus a_{i+1}\\oplus \\cdots\\oplus a_k$。 * 然后，删除","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9746"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的序列 $a_1,a_2,\\ldots a_n$。\n\n你可以对这个序列进行若干（可能为 $0$）次操作。在每次操作中，你将会：\n\n* 选择三个正整数 $i<j<k$，满足 $a_i\\oplus a_j\\oplus a_k=0$ 且 $k$ 的值不超过此时序列的长度。记 $s=a_i\\oplus a_{i+1}\\oplus \\cdots\\oplus a_k$。\n* 然后，删除 $a_i\\sim a_k$，并在原来这 $k-i+1$ 个数所在的位置插入 $s$。注意，此时序列 $a$ 的长度将会减少 $(k-i)$。\n\n请你判断是否能够使得序列 $a$ 仅剩一个数，也就是说，在所有操作结束后 $a$ 的长度为 $1$。若可以，你还需要给出一种操作方案。\n\n## Input\n\n从标准输入读入数据。\n\n**本题含有多组测试数据。**\n\n输入的第一行包含一个正整数 $T$，表示数据组数。\n\n对于每组测试数据，第一行一个正整数 $n$，表示初始序列长度。\n\n第二行 $n$ 个整数 $a_1,a_2,\\ldots,a_n$，表示初始序列中每个元素的值。\n\n## Output\n\n对于每组测试数据：\n\n+ 若存在一种方案使得序列 $a$ 仅剩一个数，请在输出的第一行输出 `Huoyu`。\n  + 接下来，在第二行你应该输出一个非负整数 $t$，表示你的操作次数。你需要保证 $0\\le t\\le n$。\n  + 接下来 $t$ 行，每行输出三个正整数 $i,j,k$，表示你在这次操作中选择的三个数的值。你需要保证 $i<j<k$ 且 $k$ 的值不超过此时序列的长度。\n+ 否则，请输出一行一个字符串 `Shuiniao`。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n对于第一组测试数据：\n\n* 第一次操作中，$a_3\\oplus a_4\\oplus a_5=1\\oplus4\\oplus5=0$，操作后的序列为 $[3,3,0]$；\n* 第二次操作中，$a_1\\oplus a_2\\oplus a_3=3\\oplus3\\oplus0=0$，操作后的序列为 $[0]$。\n\n于是，序列 $a$ 在两次操作后仅剩一个数。\n\n对于第二组测试数据：\n\n* 第一次操作，$a_1\\oplus a_3\\oplus a_4=3\\oplus6\\oplus5=0$，$s=4$，操作后的序列为 $[4,4,5,1,2,4]$。\n* 第二次操作，$a_2\\oplus a_3\\oplus a_4=4\\oplus5\\oplus1=0$，操作后的序列为 $[4,0,2,4]$。\n* 第三次操作，$a_1\\oplus a_2\\oplus a_4=4\\oplus0\\oplus4=0$，$s=2$，操作后的序列为 $[2]$。\n\n于是，序列 $a$ 在三次操作后仅剩一个数。\n\n**【样例 #2】**\n\n见选手目录下的 `merge/merge2.in` 与 `merge/merge2.ans`。\n\n这个样例满足测试点 $6\\sim7$ 的条件限制。\n\n**【样例 #3】**\n\n见选手目录下的 `merge/merge3.in` 与 `merge/merge3.ans`。\n\n这个样例满足测试点 $12\\sim13$ 的条件限制。\n\n**【数据范围】**\n\n对于所有数据保证：$1\\leq T\\leq20$，$1\\leq n\\leq500$，$0\\leq a_i<512$。\n\n| 测试点编号 | $n$ | $\\sum n\\leq$ | $a_i<$ |\n|:--:|:--:|:--:|:--:|\n| $1$ | $=1$ | $20$ | $512$ |\n| $2$ | $=2$ | $40$ | $512$ |\n| $3$ | $=3$ | $60$ | $512$ |\n| $4$ | $=4$ | $80$ | $512$ |\n| $5$ | $=5$ | $100$ | $512$ |\n| $6\\sim7$ | $\\leq40$ | $800$ | $512$ |\n| $8\\sim9$ | $\\leq70$ | $1~400$ | $512$ |\n| $10\\sim11$ | $\\leq130$ | $2~600$ | $512$ |\n| $12\\sim13$ | $\\leq300$ | $6~000$ | $128$ |\n| $14\\sim15$ | $\\leq500$ | $3~000$ | $64$ |\n| $16\\sim17$ | $\\leq500$ | $3~000$ | $128$ |\n| $18\\sim20$ | $\\leq500$ | $10~000$ | $512$ |\n\n**【提示】**\n\n$\\oplus$ 表示按位异或运算。\n\n**请对程序的常数以及效率给予充分的信任。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9746","tags":["动态规划 DP","2023","洛谷原创","Special Judge","O2优化","区间 DP","位运算","洛谷月赛"],"sample_group":[["2\n5\n3 3 1 4 5\n9\n3 4 6 5 4 5 1 2 4","Huoyu\n2\n3 4 5\n1 2 3\nHuoyu\n3\n1 3 4\n2 3 4\n1 2 4"]],"created_at":"2026-03-03 11:09:25"}}