#P12474. [2025年福建省队集训]程序攻击

    ID: 11637 传统题 1000ms 256MiB 尝试: 10 已通过: 1 难度: 10 上传者: 标签>CF3000概率论数学模拟构造枚举动态规划图论

[2025年福建省队集训]程序攻击

题目描述

这是一道通过函数与评测库交互的题。你要通过观察一个程序的运算耗时,求出该程序的隐藏参数 u,v,qu,v,q。

设 len⁡(x)\operatorname{len}(x) 为非负整数 xx 的二进制位数,即 x>0x>0 时 len⁡(x)=⌊log⁡2x⌋+1\operatorname{len}(x)=\lfloor\log_2 x\rfloor+1,规定 len⁡(0)=1\operatorname{len}(0)=1。两个整数相乘的耗时定义为 len⁡(x)len⁡(y)\operatorname{len}(x)\operatorname{len}(y)。

程序内置五个参数 u,v,k,r,qu,v,k,r,q。你给定一个 n×nn\times n 矩阵 AA,下标从 00 开始。程序首先计算 $s=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}A_{i,j}\pmod{mod}$,把 Au,vA_{u,v} 改为 (ks+r) mod mod(ks+r)\bmod mod,再用矩阵快速幂计算修改后的 AqA^q。所有矩阵运算均对 modmod 取模。每次询问返回所有乘法的耗时之和,包含计算 ksks 的乘法。

本站随题提供的 grader.cpp 在修改矩阵后以单位矩阵初始化 BB。它依次处理 qq 的第 00 到第 3030 位。若当前位为 11,计算 B←BAB\leftarrow BA。无论当前位是什么,都会计算 A←A2A\leftarrow A^2,包括处理第 3030 位之后的这次平方。每次矩阵乘法执行全部 n3n^3 次标量乘法,包括操作数为 00 的乘法。原比赛说明正式交互库与样例库可能不同,解法不能依赖交互库的私有变量、内部内存或输入输出。

提交接口

包含 attack.h,不编写 main,实现以下函数:

void solve(int n, int mod, int &u, int &v, int *qs);

评测库会把矩阵大小 nn 和模数 modmod 传给你。返回前须把 u,vu,v 赋为正确值,并将最多 500500 个候选值写入 qs[0] 到 qs[499],其中至少一个候选值须等于真正的 qq。

可以调用 int get_time(Matrix A);。令每个矩阵元素取 [0,mod)[0,mod) 中的整数。该函数返回上述程序在输入 AA 时的耗时,每个测试点最多调用 5×1045\times10^4 次。

也可以调用下面的函数直接查询隐藏参数。每个函数只在第一次调用时扣分,扣除值按该测试点原始分数计算。测试点分数最低为 00。

函数 返回参数 扣分
int get_u(); uu 10%
int get_v(); vv
int get_k(); kk 20%
int get_r(); rr
int get_q(); qq 80%

如果返回的 u,vu,v 不正确、候选值中没有真实的 qq,或调用 get_time 超过上限,则该测试点得 00 分。不得直接与标准输入输出流交互,或绕过接口读取隐藏参数。

本地测试输入与输出

下发的 grader.cpp 是样例评测库,attack.h 是接口头文件,attack.cpp 是样例程序。可在本地编译:

g++ -o attack attack.cpp grader.cpp -O2 -std=c++14

编译得到的本地测试程序从标准输入读取一行七个整数 n,mod,u,v,k,r,qn,mod,u,v,k,r,q,并向标准输出写出测试信息和分数。提交的 solve 仍应使用上述接口。

数据范围与约定

对于所有数据,modmod 是素数,0≤u,v<n0\le u,v<n,1≤k,r,q<mod1\le k,r,q<mod。数据在合法范围内等概率随机生成。

测试点 nn modmod 的范围
1 27<mod<282^7<mod<2^8
2–5 2 215<mod<2162^{15}<mod<2^{16}
6–10 230<mod<2312^{30}<mod<2^{31}

原 PDF 题面