测测你的稀疏矩阵向量乘法-scale23 排行榜
时间限制: 15 s
空间限制: 2097152 KB
题目描述
给定一个 n * n 的随机稀疏矩阵 A 和长度为 n 的随机向量 x,计算 A^20 * x。所有乘法与加法均在模 2^32 意义下进行,要求结果准确一致。
矩阵以 m 条 COO 记录给出。每条记录具有 src、dst、weight 三个32位无符号整数,表示向 A[src][dst] 加上 weight。不同记录可以具有相同的 src、dst,此时权重按模 2^32 累加;自环与零权重均保留。因此,m 表示记录条数,不是去重后的非零位置数。
接口
cpp
struct Edge { unsigned src, dst, weight; };
void sparse_power20(unsigned n, unsigned m, const Edge *A,
const unsigned *x, unsigned *out);
A[0..m) 给出上述 COO 记录,x[0..n) 给出初始向量。将 A^20 * x 的第 i 个元素写入 out[i]。A、x、out 的起始地址均按 4 KiB 对齐;A 和 x 仅供读取,out 仅用于输出,调用前全部清零,可写范围为 n 个 unsigned。
随机数据生成
稀疏结构采用下面明确约定的有向 Graph500 Kronecker 生成算法。只对随机种子保密;算法、常量、生成顺序均公开。每个测试点使用固定种子。
记 scale = log2(n),所有顶点编号从 0 到 n-1,依次生成编号为 k = 0, 1, ..., m-1 的边。不进行 clip-and-flip,不补反向边,不删除自环或重复边,也不另外打乱边的顺序。
MRG 随机数发生器
状态为五元组 (z1,z2,z3,z4,z5),模数 M=2147483647。初始五元组是保密种子,各分量属于 [1,M-1]。一次取数执行:
text
t = (107374182*z1 + 104480*z5) mod M
(z1,z2,z3,z4,z5) = (t,z1,z2,z3,z4)
return t
用 T 表示一次状态转移,T^q(S) 表示从状态 S 连续执行 q 次转移后的状态;实际生成器用矩阵快速幂计算跳跃,与连续执行的定义完全相同。
每条边的未重编号端点
设初始状态为 S。第 k 条边从独立跳跃状态 T^(k*2^64)(S) 开始取数,初始 a=b=0。重复以下过程 scale 次:
- 从该状态取数
r;若r<3647,重新取数,直到r>=3647。 - 令
q=r mod 10000,按下表取位(u,v)。 - 执行
a=2*a+u、b=2*b+v。
| q 的范围 | (u,v) | 概率 |
| --- | --- | --- |
| 0 <= q < 1900 | (0,1) | 0.19 |
| 1900 <= q < 3800 | (1,0) | 0.19 |
| 3800 <= q < 9500 | (0,0) | 0.57 |
| 9500 <= q < 10000 | (1,1) | 0.05 |
各层使用相同的概率,不引入额外噪声。
顶点重编号
另从状态 T^(50*2^128+7*2^64)(S) 连续取四个数 r0,r1,r2,r3,定义
text
val0 = r0*(2^32-1)+r1
val1 = r2*(2^32-1)+r3
对 a、b 分别调用同一个 scramble,结果作为 src、dst。以下伪代码的变量均为64位无符号整数,加法、乘法按模 2^64 计算;reverse64 反转全部64个二进制位,| 为按位或。
cpp
uint64_t scramble(uint64_t v) {
v += val0 + val1;
v *= val0 | 0x4519840211493211ULL;
v = reverse64(v) >> (64 - scale);
v *= val1 | 0x3050852102C843A5ULL;
v = reverse64(v) >> (64 - scale);
return v;
}
边权与初始向量
边权与初始向量分别使用独立的保密64位无符号初始状态。每次取数使用以下 SplitMix64 算法;所有64位运算均按模 2^64 进行,返回值为低32位。按边的编号递增顺序产生 weight,按元素编号递增顺序产生 x[i]。
cpp
uint32_t next_value(uint64_t &state) {
uint64_t z = (state += 0x9e3779b97f4a7c15ULL);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return uint32_t(z ^ (z >> 31));
}
两个流的结果均属于 [0, 2^32),允许为零。两个流的种子相互独立,也独立于稀疏结构的五元组种子。
数据范围
n 等于 2^23,m 等于 2^27。
题目来源
saffah_codex_maker
关于接口中的数组初值说明(最后更新:2023年2月6日)
若题目要求实现函数接口,且该函数中存在仅用于输出的数组(如 void solve(int n, const int *in, int *out) 中的 out),那么除非另外说明,否则该数组在程序启动时的初值为 0。
关于标准输出的说明(最后更新:2018年10月23日)
标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。
如果你的程序要进行大量输出,请考虑这一点。
关于提交的说明
你提交的代码将会被公开,所有人都可见。如果这不是你所期望的,或者如果想要删除已提交的代码,请联系管理员。
Judge Duck Online | 评测鸭在线
Server Time: 2026-11-19 09:41:14 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠