牛客练习赛18th D 矩阵

题目描述 

给定两个巨大的方块矩阵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) 的结果

示例1

输入

1 2 3 4 5 6 7 8 9 10

输出

50873769

示例2

输入

2 3 4 5 6 7 8 9 10 11

输出

891416296

示例3

输入

7000 7001 7002 7003 7004 7005 7006 7007 7008 7009

输出

276810293

备注:

1 ≤ n ≤ 7000
1 ≤Aa，Ab，Ac，Ad，Ba，Bb，Bc，Bd < 232
2 ≤ p < 109+ 7

官方题解:

但是这里实际我们不能开[7000][7000]的数组.会MLE

但是我们可以用A[k] 表示  用B[k]表示  

于是我们在随机生成矩阵元素时就可以计算出A[],B[].

p的n次方数组也需要预先打表出来,因为直接计算的话会超时.

时间复杂度O(n^2)

代码:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn = 10000;
unsigned int x, y, z, w;
const ll mod = 1e9+7;
ll xorshift() {
    unsigned int t = x;  /// 把这改成了ll后 wan了不知道多少次,以后给的函数最好别改
    t ^= t << 11;
    t ^= t >> 8;
    x = y; y = z; z = w;
    w ^= w >> 19;
    w ^= t;
    return w&((1<<24)-1);
}
ll A[maxn],B[maxn],At[maxn],Bt[maxn];

int main()
{
    int n;
    ll a,b,c,d,aa,bb,cc,dd,p;
    while(~scanf("%d",&n))
    {
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        scanf("%lld%lld%lld%lld",&aa,&bb,&cc,&dd);
        scanf("%lld",&p);
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        
        Bt[n-1] = 1;
        for(int i=n-2;i>=0;i--) Bt[i] = Bt[i+1] * p % mod;
        At[n-1] = 1;
        if(n > 1) At[n-2] = Bt[0] * p % mod;
        for(int i=n-3;i>=0;i--) At[i] = At[i+1] * At[n-2] % mod;  
        
        x = a; y = b; z = c; w = d;
        for(int i=0;i<n;i++) for(int j=0;j<n;j++) 
            A[j] = (A[j] + xorshift()%mod*At[i])%mod;
        x = aa;y = bb;z = cc;w = dd;
        for(int i=0;i<n;i++) for(int j=0;j<n;j++)
            B[i] = (B[i] + xorshift()%mod*Bt[j])%mod;
        ll ans = 0;
        for(int i=0;i<n;i++) ans = (ans+A[i]*B[i])%mod; 
        printf("%lld\n",ans);
    }
    return 0;
}