测测你的稀疏矩阵向量乘法-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 次:

  1. 从该状态取数 r;若 r<3647,重新取数,直到 r>=3647。
  2. 令 q=r mod 10000,按下表取位 (u,v)。
  3. 执行 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
个人娱乐项目,仅供学习交流使用 | 捐赠