{"problem":{"name":"[THUPC 2023 决赛] Freshman Dream","description":{"content":"小 J 正在学习矩阵乘法。 一旁的小 L 告诉他：只要将两个矩阵对应的位置乘起来，那就能得到两个矩阵的乘法了。 这当然是不对的，但是小 L 要继续骗小 J。为此，她需要在自己的 OJ 上放一道矩阵乘法题，使得这样的矩阵乘法也能得到正确的答案。 因为小 L 的 OJ 跑的很慢并且空间限制也很小，所以这道矩阵乘法题的答案都是 $\\bmod 2$ 意义下的。 现在小 L 开始造数据。她先随机生成","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9382"},"statements":[{"statement_type":"Markdown","content":"小 J 正在学习矩阵乘法。\n\n一旁的小 L 告诉他：只要将两个矩阵对应的位置乘起来，那就能得到两个矩阵的乘法了。\n\n这当然是不对的，但是小 L 要继续骗小 J。为此，她需要在自己的 OJ 上放一道矩阵乘法题，使得这样的矩阵乘法也能得到正确的答案。\n\n因为小 L 的 OJ 跑的很慢并且空间限制也很小，所以这道矩阵乘法题的答案都是 $\\bmod 2$ 意义下的。\n\n现在小 L 开始造数据。她先随机生成了一个 $n\\times n$ 的矩阵 $A$，具体地，每一个元素以 $\\frac 12$ 的概率为 $1$，剩下的概率为 $0$，且这些事件相互独立。现在，她还要设计另一个 $n\\times n$  的 $01$ 矩阵 $B$，使得 $AB_{ij}\\equiv A_{ij}B_{ij}\\pmod 2$。\n\n小 L 试图随机生成矩阵，但是找不出什么满足要求的矩阵；她试图构造几个矩阵，发现只会构造全 $0$ 矩阵，这太明显了。现在，她将生成数据的重任交给了你，你需要给出一个满足要求的 $B$，同时为了不让大家看出数据有猫腻，她还额外要求了 $B$ 里面恰好有 $k$ 个 $1$。\n\n## Input\n\n从标准输入读入数据。\n\n输入的第一行包含两个正整数 $n,k$，表示矩阵的大小和题目中的 $k$。\n\n接下来 $n$ 行，每一行 $n$ 个整数 $a_{ij}$ 表示 $A$ 的元素。\n\n## Output\n\n输出到标准输出。\n\n如果没有任何 $B$ 满足要求，输出一行一个整数 $-1$。\n\n否则，先输出一行一个整数 $1$，然后输出 $n$ 行，每行 $n$ 个 $\\{0,1\\}$ 中的整数来表示 $B$ 矩阵的元素。如果有多个可能的 $B$，输出其中一个即可。\n\n[samples]\n\n## Note\n\n**【样例说明 #1】**\n\n这里的 $A$ 是单位矩阵，构造的 $B$ 也是单位矩阵，乘积也为单位矩阵。同时，将对应位置相乘也为单位矩阵，并且 $B$ 中恰有 $k=3$ 个 $1$，故满足要求。\n\n本样例中 $n$ 不为 $100$，但保证所有测试数据中 $n$ 均为 $100$。\n\n**【数据范围】**\n\n对于所有测试数据，$n=100$，$0 \\le k \\le n^2$，$a_{ij}\\in \\{0,1\\}$，所有 $a_{ij}$ 均为独立均匀随机。\n\n**【题目来源】**\n\n来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。\n\n题解等资源可在 <https://github.com/THUSAAC/THUPC2023> 查看。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9382","tags":["2023","Special Judge","O2优化","线性基","THUPC"],"sample_group":[["3 3\n1 0 0\n0 1 0\n0 0 1","1\n1 0 0\n0 1 0\n0 0 1"]],"created_at":"2026-03-03 11:09:25"}}