P9382 [THUPC 2023 决赛] Freshman Dream

题目描述

小 J 正在学习矩阵乘法。 一旁的小 L 告诉他:只要将两个矩阵对应的位置乘起来,那就能得到两个矩阵的乘法了。 这当然是不对的,但是小 L 要继续骗小 J。为此,她需要在自己的 OJ 上放一道矩阵乘法题,使得这样的矩阵乘法也能得到正确的答案。 因为小 L 的 OJ 跑的很慢并且空间限制也很小,所以这道矩阵乘法题的答案都是 $\bmod 2$ 意义下的。 现在小 L 开始造数据。她先随机生成了一个 $n\times n$ 的矩阵 $A$,具体地,每一个元素以 $\frac 12$ 的概率为 $1$,剩下的概率为 $0$,且这些事件相互独立。现在,她还要设计另一个 $n\times n$ 的 $01$ 矩阵 $B$,使得 $AB_{ij}\equiv A_{ij}B_{ij}\pmod 2$。 小 L 试图随机生成矩阵,但是找不出什么满足要求的矩阵;她试图构造几个矩阵,发现只会构造全 $0$ 矩阵,这太明显了。现在,她将生成数据的重任交给了你,你需要给出一个满足要求的 $B$,同时为了不让大家看出数据有猫腻,她还额外要求了 $B$ 里面恰好有 $k$ 个 $1$。

输入格式

输出格式

说明/提示

**【样例说明 #1】** 这里的 $A$ 是单位矩阵,构造的 $B$ 也是单位矩阵,乘积也为单位矩阵。同时,将对应位置相乘也为单位矩阵,并且 $B$ 中恰有 $k=3$ 个 $1$,故满足要求。 本样例中 $n$ 不为 $100$,但保证所有测试数据中 $n$ 均为 $100$。 **【数据范围】** 对于所有测试数据,$n=100$,$0 \le k \le n^2$,$a_{ij}\in \{0,1\}$,所有 $a_{ij}$ 均为独立均匀随机。 **【题目来源】** 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2023)决赛。 题解等资源可在 查看。