题号：NC15967
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
给定两个巨大的方块矩阵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，Aa，Ab，Ac，Ad，Ba，Bb，Bc，Bd，p。
矩阵A是通过n，Aa，Ab，Ac，Ad构建getInputMatrix()的。
矩阵B是通过n，Ba，Bb，Bc，Bd构建getInputMatrix()的。
p是哈希函数。
输出描述:
令 C = A * B， C 是A矩阵乘以 B 的结果
请输出一个整数，它是 hash(n,C,p) 的结果
示例3
输入
复制
7000 7001 7002 7003 7004 7005 7006 7007 7008 7009
备注:
1 ≤ n ≤ 7000
1 ≤Aa，Ab，Ac，Ad，Ba，Bb，Bc，Bd < 232
2 ≤ p < 109+ 7