#P6695. [2019山东省队集训第一轮]心的旋律

    ID: 6545 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-构造与建模图构造组合数学补集计数Pascal 递推字典序排名与反排名CF2700

[2019山东省队集训第一轮]心的旋律

[2019山东省队集训第一轮]心的旋律

题目背景

いつの日も歌おう

この心のまま/曾几何时咏唱着的心的旋律

響くよ 空の向こう彼方まで/会响彻天空,传到遥远的彼岸

そしてまたどこかで

君に届いたら/如果这首歌能再次传到你的耳中

思い出して欲しい/希望你能够想起

きらめく瞳で過ごした日々を/那些双眸闪耀着光辉的日子

輝く笑顔で過ごした日々を/那些绽放着笑容的日子

题目描述

构造一张左右两侧各有 nn 个结点的二分图。对于左侧结点的任意子集 AA,定义 F(A)F(A) 为右侧至少与 AA 中一个结点相邻的结点集合。

给定 n,Kn,K,要求在左侧的全部 2n2^n 个子集 AA 中,恰有 KK 个满足

∣F(A)∣<∣A∣.\lvert F(A)\rvert<\lvert A\rvert.

空集也包含在所考察的子集中。如果有多种构造,输出任意一种;如果无解,输出 −1-1。

输入格式

输入一行两个整数 n,Kn,K。

输出格式

若无解,输出一行 −1-1。

否则,输出一个 n×nn\times n 的 0/10/1 矩阵,矩阵元素用空格分隔。第 ii 行第 jj 列为 11 表示左侧结点 ii 与右侧结点 jj 之间有边,为 00 表示没有边。

样例输入 1

2 0

样例输出 1

1 0
0 1

样例解释 1

对于每个子集 AA,都有 ∣F(A)∣=∣A∣\lvert F(A)\rvert=\lvert A\rvert。

样例输入 2

2 1

样例输出 2

1 0
1 0

数据范围

所有数据满足 1≤n≤321\le n\le32,0≤K≤2n0\le K\le2^n。

子任务 分值 nn 的上界 KK 的限制
1 10 分 33 无
2 5 分 66
3 15 分 1010
4 10 分 2020 K=2xK=2^x
5 20 分 无
6 40 分 3232