给定两个巨大的方块矩阵A和B .请输出A x B 的运算结果，且时限只有 2s， 哈哈！对矩阵乘法的演进历史有些涉猎的人，应该能感受到在 某CPC 上出现这样的题目有多不合理， 为了使这个问题成为可能（？），我们将减小I / O大小， 现在，给定a，b，c，d的四个种子可以通过Xorshift随机数生成器生成输入矩阵， 这里是通过随机数生成器来产生矩阵的实现： uint32_t x, y, z, w;
给定两个巨大的方块矩阵A和B (行数高达 7000).请输出A x B 的运算结果，且时限只有 2s。 哈哈！对矩阵乘法的演进历史有些涉猎的人，应该能感受到在 某CPC 上出现这样的题目有多不合理。 为了使这个问题成为可能（？），我们将减小I / O大小。 现在，给定a，b，c，d的四个种子可以通过Xorshift随机数生成器生成输入矩阵。 这里是通过随机数生成器来产生矩阵的实现： uint32_t x, y, z, w; uint32_t xorshift() { uint32_t t = x; t ^= t << 11; t ^= t >> 8; x = y; y = z; z = w; w ^= w >> 19; w ^= t; return w & ((1 << 24) - 1); } void getInputMatrix( int n, uint32_t matrix[][7000], uint32_t a, uint32_t b, uint32_t c, uint32_t d ) { x = a; y = b; z = c; w = d; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { matrix[i][j] = xorshift(); } } } 另外，您应该将输出矩阵传递给哈希函数(hash function)。 我们会给你另一个数字p来做这件事。 这里是哈希函数的实现。 const int MOD = 1000000007; int hash(int n, long long matrix[][7000], int p) { long long v = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { v *= p; v += matrix[i][j]; v %= MOD; } } return v; } P.S. 不懂 C++语法的同学们就抱歉啦～
标签： HBC15967矩阵题解
