UOJ Logo Universal Online Judge

UOJ

#655. 【ULR #2】跳蚤猜密码

附件下载 统计

这是一道交互题。

跳蚤国王发现通过后门破解密码,可能要等到 2050 年了。

因此,跳蚤国王觉得直接破解开机密码或许更为高效。

国王的密码可以被表示为一个神秘的 n 阶矩阵 A,它的元素都是 0998244352 之间的整数。

国王发现尽管无法直接获得开机密码。但是可以通过 Linux 跳蚤版的漏洞获得关于密码的信息。

具体来说,你可以向交互库进行若干次询问,每次给定交互库另一个元素都是 0998244352 之间整数的 n 阶矩阵 B,交互库会返回 det(A+B)998244353 取模的值。因为安全限制,你最多只能进行 T 次询问。

你的任务是帮助国王猜测出原来的矩阵 A

这里 det(A) 表示方阵 A 的行列式。

任务

本题只支持C++。

你必须引用 password.h 头文件。

你需要实现下面的过程:

std::vector<int> solve(int n,int T);

其中 n 是矩阵 A 的阶数,T 是你最多的询问次数。你需要返回一个长度恰为 n2vector,里面依次列出矩阵 A 的所有元素,其中下标为 (i1)×n+j1 的位置为矩阵 A(i,j) 位置元素 Ai,j

你可以调用以下过程和交互库进行交互:

int query(std::vector<int> vt);

其中 vt 是一个长度恰为 n2vector,里面依次列出你这次给定的矩阵 B 的所有元素,其中下标为 (i1)×n+j1 的位置为矩阵 B(i,j) 位置元素 Bi,j。交互库会返回 det(A+B)998244353 取模的值。你必须保证 vt 中所有元素都在 0998244352 之间且长度为 n2,不然交互库会返回 1 且你的交互过程会被判定为失败。你至多只能调用 Tquery 函数。

评测方式

样例评测库将读入如下格式的输入数据:

第一行包括两个正整数 nT,表示矩阵 A 的阶数与你最多的询问次数。

接下来 n 行,每行 n 个整数,其中第 i 行第 j 个整数为矩阵 A(i,j) 位置元素 Ai,j

在最终测试中,矩阵 A 是确定的,不会因为你的询问而改变。

样例评测库将输出如下格式的输出数据:

对于每一组数据,如果你正确猜测出了矩阵 A 且询问次数没有超过限制次数,会输出你的询问次数 cnt,否则会输出 Wrong Answer.

样例一

input

1 1
2

output

1

explanation

你可以直接调用 query([0]) 来得到 det(A),由于 n=1,这正好也是 A 的唯一一个元素。

数据范围

对于所有数据,1n50,1T8000,0Ai,j998244352

保证若你的交互过程满足题目限制,交互库不会占用超过 0.5s 时间和 32MB 内存。

子任务编号 n T= 分值
1 2 5 14
2 2 4 6
3 20 8000 24
4 50 2501 27
5 50 2500 29

时间限制2s

空间限制512MB

下载

样例数据与样例评测库下载