矩阵__牛客网

给定两个巨大的方块矩阵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++语法的同学们就抱歉啦～

输入只包含一行，包含十个整数n，A_a，A_b，A_c，A_d，B_a，B_b，B_c，B_d，p。
矩阵A是通过n，A_a，A_b，A_c，A_d构建getInputMatrix()的。
矩阵B是通过n，B_a，B_b，B_c，B_d构建getInputMatrix()的。
p是哈希函数。

矩阵

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题