HBC54635Alternating Sum,逆元,数学,数论[CSP2019]格雷码（code)题解

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

已替换官方数据 通常，人们习惯将所有 n位二进制串按照字典序排列，例如所有2位二进制串按字典序从小到大排列为： 00， 01， 10， 11， 格雷码（Gray Code）是一种特殊的 n位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻， 所有 2位二进制串按格雷码排列的一个例子为： 00， 01， 11， 10， n 位格

已替换官方数据 通常，人们习惯将所有 n位二进制串按照字典序排列，例如所有2位二进制串按字典序从小到大排列为： 00， 01， 10， 11。 格雷码（Gray Code）是一种特殊的 n位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。 所有 2位二进制串按格雷码排列的一个例子为： 00， 01， 11， 10。 n 位格雷码不止一种，下面给出其中一种格雷码的生成算法：  1位格雷码由两个1 位二进制串组成，顺序为：0， 1。 n+1位格雷码的前2n2^n2n 个二进制串，可以由依此算法生成的 n 位格雷码（总共2n2^n2n 个 n 位二进制串）按顺序排列，再在每个串前加一个前缀 0 构成。 n + 1 位格雷码的后 2n2^n2n 个二进制串，可以由依此算法生成的 n 位格雷码（总共2n2^n2n 个 n 位二进制串）按逆序排列，再在每个串前加一个前缀 1 构成。 综上， n + 1 位格雷码，由 n 位格雷码的 2n2^n2n 个二进制串按顺序排列再加前缀 0，和按逆序排列再加前缀 1 构成，共2n+12^{n+1}2n+1 个二进制串。另外，对于 n 位格雷码中的2n2^n2n 个二进制串，我们按上述算法得到的排列顺序将它们从0∼2n−10 ∼ 2^{n − 1}0∼2n−1 编号。 按该算法， 2 位格雷码可以这样推出： 已知 1 位格雷码为 0， 1。  前两个格雷码为 0 1， 0 1。后两个格雷码为 1 1， 1 0。合并得到 00， 01， 11， 10，编号依次为 0 ∼ 3。 同理， 3 位格雷码可以这样推出： 已知 2 位格雷码为： 00， 01， 11， 10。 前四个格雷码为：0 00， 0 01， 0 11， 0 10。后四个格雷码为：1 10， 1 11， 1 01，1 00。合并得到： 000， 001， 011， 010， 110， 111， 101， 100，编号依次为 0 ∼ 7。 现在给出 n, k，请你求出按上述算法生成的 n 位格雷码中的 k 号二进制串。

不断学习，不断挑战，才能在编程领域中脱颖而出！全网最全C++题库，助您成为编程高手！

标签： HBC54635Alternating Sum 逆元 数学 数论[CSP2019]格雷码（code)题解