{"trustable":false,"sections":[{"title":"题目大意","value":{"format":"MD","content":"RAID 技术采用多个磁盘保存数据,每份数据在不止一个磁盘上被保存,因此在某个磁盘损坏时能通过其他磁盘恢复数据。本题讨论其中一种 RAID 技术。数据被划分成大小为 $s(1\\le s\\le 64)$ 比特的数据块保存在 $d$ 个磁盘上,如下表所示,每 $d-1$ 个数据块都有一个校验块,使得每 $d$ 个数据块的异或结果全为 $0$(偶校验)或全为 $1$(奇校验)。\n\n|磁盘 $1$|磁盘 $2$|磁盘 $3$|磁盘 $4$|磁盘 $5$|\n|:-:|:-:|:-:|:-:|:-:|\n|**数据块 $\\mathbf{1\\sim 4}$ 的校验块**|数据块 $1$|数据块 $2$|数据块 $3$|数据块 $4$|\n|数据块 $5$|**数据块 $\\mathbf{5\\sim 8}$ 的校验块**|数据块 $6$|数据块 $7$|数据块 $8$|\n|数据块 $9$|数据块 $10$|**数据块 $\\mathbf{9\\sim 12}$ 的校验块**|数据块 $11$|数据块 $12$|\n|数据块 $13$|数据块 $14$|数据块 $15$|**数据块 $\\mathbf{13\\sim 16}$ 的校验块**|数据块 $16$|\n|数据块 $17$|数据块 $18$|数据块 $19$|数据块 $20$|**数据块 $\\mathbf{17\\sim 20}$ 的校验块**|\n|**数据块 $\\mathbf{21\\sim 24}$ 的校验块**|数据块 $21$|数据块 $22$|数据块 $23$|数据块 $24$|\n|数据块 $25$|**数据块 $\\mathbf{25\\sim 28}$ 的校验块**|数据块 $26$|数据块 $27$|数据块 $28$|\n\n例如,$d\u003d5,s\u003d2$,偶校验,数据 `6C7A79EDFC`(其二进制为 `0110110001111010011110011110110111111100`)的保存方式如下:\n\n```plaintext\nD1|D2|D3|D4|D5\n--+--+--+--+--\n00|01|10|11|00\n__| | | | \n01|10|11|10|10\n |__| | | \n01|11|01|10|01\n | |__| | \n11|10|11|11|01\n | | |__| \n11|11|11|00|11\n | | | |__\n```\n其中带下划线的块是校验块。输入 $d,s,b$、校验种类(`E` 为偶校验,`O` 为奇校验)以及 $b$ 个数据块(其中 `?` 表示损坏的数据),你的任务是恢复并输出完整的数据。如果校验错或者由于损坏数据过多无法恢复,应报告磁盘非法。\n\n提示:本题是位运算的不错练习,但如果没有 RAID 的知识背景,上述简要翻译可能较难理解,细节建议参考原题。"}},{"title":"样例","value":{"format":"MD","content":"输入\n```plaintext\n5 2 5\nE\n0001011111\n0110111011\n1011011111\n1110101100\n0010010111\n3 2 5\nE\n0001111111\n0111111011\nxx11011111\n3 5 1\nO\n11111\n11xxx\nx1111\n0\n```\n\n输出\n```plaintext\nDisk set 1 is valid, contents are: 6C7A79EDFC\nDisk set 2 is invalid.\nDisk set 3 is valid, contents are: FFC\n```"}}]}