#P12474. [2025年福建省队集训]程序攻击
[2025年福建省队集训]程序攻击
题目描述
这是一道通过函数与评测库交互的题。你要通过观察一个程序的运算耗时,求出该程序的隐藏参数 。
设 为非负整数 的二进制位数,即 时 ,规定 。两个整数相乘的耗时定义为 。
程序内置五个参数 。你给定一个 矩阵 ,下标从 开始。程序首先计算 $s=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}A_{i,j}\pmod{mod}$,把 改为 ,再用矩阵快速幂计算修改后的 。所有矩阵运算均对 取模。每次询问返回所有乘法的耗时之和,包含计算 的乘法。
本站随题提供的 grader.cpp 在修改矩阵后以单位矩阵初始化 。它依次处理 的第 到第 位。若当前位为 ,计算 。无论当前位是什么,都会计算 ,包括处理第 位之后的这次平方。每次矩阵乘法执行全部 次标量乘法,包括操作数为 的乘法。原比赛说明正式交互库与样例库可能不同,解法不能依赖交互库的私有变量、内部内存或输入输出。
提交接口
包含 attack.h,不编写 main,实现以下函数:
void solve(int n, int mod, int &u, int &v, int *qs);
评测库会把矩阵大小 和模数 传给你。返回前须把 赋为正确值,并将最多 个候选值写入 qs[0] 到 qs[499],其中至少一个候选值须等于真正的 。
可以调用 int get_time(Matrix A);。令每个矩阵元素取 中的整数。该函数返回上述程序在输入 时的耗时,每个测试点最多调用 次。
也可以调用下面的函数直接查询隐藏参数。每个函数只在第一次调用时扣分,扣除值按该测试点原始分数计算。测试点分数最低为 。
| 函数 | 返回参数 | 扣分 |
|---|---|---|
int get_u(); |
10% | |
int get_v(); |
||
int get_k(); |
20% | |
int get_r(); |
||
int get_q(); |
80% |
如果返回的 不正确、候选值中没有真实的 ,或调用 get_time 超过上限,则该测试点得 分。不得直接与标准输入输出流交互,或绕过接口读取隐藏参数。
本地测试输入与输出
下发的 grader.cpp 是样例评测库,attack.h 是接口头文件,attack.cpp 是样例程序。可在本地编译:
g++ -o attack attack.cpp grader.cpp -O2 -std=c++14
编译得到的本地测试程序从标准输入读取一行七个整数 ,并向标准输出写出测试信息和分数。提交的 solve 仍应使用上述接口。
数据范围与约定
对于所有数据, 是素数,,。数据在合法范围内等概率随机生成。
| 测试点 | 的范围 | |
|---|---|---|
| 1 | ||
| 2–5 | 2 | |
| 6–10 | ||