#P12706. 并非呃呃

并非呃呃

题目背景

给你一张 nn 个点的简单无向图。

接下来有 qq 次操作,每次操作为添加一条边或删去一条边,请在每次操作后判断图中是否有四元环。

等等,题面放错了。

并非呃呃。


在「呃呃 / ee」一题中,如何构造数据成为了一个难题。

当初始边数过小时,可能会让一些 O(mm)O(m\sqrt m) 的做法得以通过,而初始边数过大时又随机不出一张无四元环的初始图。

给你一道呃呃,输出一组足够强力的数据。

题目描述

给你一个整数 nn,有一集合 U={1,2,,n}U=\{1,2,\dots,n\}

你需要构造 nn 个集合 S1,2,,nS_{1,2,\dots ,n},满足条件:

  • 对所有 1in1\le i \le nSiUS_i\sube U
  • 对所有 1i<jn1\le i<j\le nSiSj1|S_i\cap S_j|\le 1

为了不让暴力通过,你希望 i=1nSi\displaystyle\sum_{i=1}^n|S_i| 尽量大。

输入格式

一行两个整数 n,Ln,L,关于 LL 的信息见「数据规模与约定」部分。

输出格式

输出 nn 行,每行一个长为 nn 的 01 字符串。

若第 ii 行第 jj 列的字符为 1,代表 jSij\in S_i,否则 jSij\notin S_i

3 5
111
010
100

提示

数据规模与约定

为了衡量你的构造强度,你将会得到一个整数 LL

对于每个数据点,你需要构造出一组解使得 i=1nSiL\sum_{i=1}^n|S_i|\ge L

数据点编号 n=n= L=L=
11 44 88
22 1010 2323
33 23332333 46664666
44 69966996
55 10410^4
66 2×1042\times 10^4
77 4×1044\times 10^4
88 6×1046\times 10^4
99 8×1048\times 10^4
1010 10510^5

对于所有数据,保证 4n23334\le n\le 2333

提示

构造一张左右部点数均为 nn 的二分图,对于所有 1i,jn1\le i,j\le n,左侧点 ii 与右侧点 jj 之间有边当且仅当 jSij\in S_i。容易验证,此时构造出的图中无四元环。