uoj#P655. 【ULR #2】跳蚤猜密码

【ULR #2】跳蚤猜密码

这是一道交互题。

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

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

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

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

具体来说,你可以向交互库进行若干次询问,每次给定交互库另一个元素都是 $0\sim 998244352$ 之间整数的 $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$ 是你最多的询问次数。你需要返回一个长度恰为 $n^2$ 的 vector,里面依次列出矩阵 $A$ 的所有元素,其中下标为 $(i-1)\times n+j-1$ 的位置为矩阵 $A$ 的 $(i,j)$ 位置元素 $A_{i,j}$。

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

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

其中 vt 是一个长度恰为 $n^2$ 的 vector,里面依次列出你这次给定的矩阵 $B$ 的所有元素,其中下标为 $(i-1)\times n+j-1$ 的位置为矩阵 $B$ 的 $(i,j)$ 位置元素 $B_{i,j}$。交互库会返回 $\det(A+B)$ 对 $998244353$ 取模的值。你必须保证 vt 中所有元素都在 $0\sim 998244352$ 之间且长度为 $n^2$,不然交互库会返回 $-1$ 且你的交互过程会被判定为失败。你至多只能调用 $T$ 次 query 函数。

评测方式

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

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

接下来 $n$ 行,每行 $n$ 个整数,其中第 $i$ 行第 $j$ 个整数为矩阵 $A$ 的 $(i,j)$ 位置元素 $A_{i,j}$。

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

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

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

1 1
2
1

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

数据范围

对于所有数据,$1\leq n\leq 50,1\leq T\leq 8000,0\leq A_{i,j}\leq 998244352$。

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

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

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

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