#P15894. [Roi2021 Team]Balanced Illumination / 平衡彩灯

    ID: 15105 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-格雷码递归构造序列构造奇偶性分析

[Roi2021 Team]Balanced Illumination / 平衡彩灯

题目描述

圣比茨堡政府正在准备新年城市装饰方案。广场上将有一串包含 nn 盏灯的彩灯,每盏灯有两种状态:亮或灭。

彩灯每秒改变一次外观。每次变化时,必须恰好有一盏灯改变状态,即从亮变灭,或从灭变亮。设计师希望所有可能的灯光组合以 2n2^n 秒为周期循环出现,并且在一个周期内,所有 2n2^n 种组合都恰好出现一次。

工程师指出,如果某些灯频繁开关,更容易损坏。因此要求每盏灯的状态变化次数尽量均衡。

你需要构造一个长度为 2n2^n 的组合序列 a0,a1,…,a2n−1a_0,a_1,\ldots,a_{2^n-1}。每个 aka_k 是长度为 nn 的 01 串,其中第 ii 位为 1 表示第 ii 盏灯亮,为 0 表示灭。要求:

  1. 所有组合两两不同;
  2. 相邻两个组合恰好一位不同;
  3. 最后一个组合 a2n−1a_{2^n-1} 与第一个组合 a0a_0 也恰好一位不同;
  4. 设 cic_i 为第 ii 盏灯在完整周期内状态变化的次数,包括从 a2n−1a_{2^n-1} 回到 a0a_0 的那次变化。对任意 i≠ji \ne j,cic_i 与 cjc_j 的差不超过 22。

请输出任意满足条件的方案。

输入格式

输入一个整数 nn。

输出格式

输出 2n2^n 行,每行一个长度为 nn 的 01 串,表示一个满足要求的灯光组合序列。

保证一定存在满足条件的方案。

数据范围

1≤n≤171 \le n \le 17。

样例 1

输入:
3

输出:
000
010
011
111
110
100
101
001

样例 2

输入:
4

输出:
0000
0010
1010
1011
0011
0111
0110
0100
0101
0001
1001
1101
1111
1110
1100
1000

样例说明

第一个样例中,三盏灯的变化次数分别为 2,2,42,2,4。
第二个样例中,四盏灯的变化次数均为 44。