202305-2-矩阵运算

一、题目分析

此题本质是计算$(W\cdot (Q\times K^T))\times V$的值。
注意任务要求：

70% 的测试数据满足：n<=100且d<=10 。输入矩阵、向量中的元素均为整数，且绝对值均不超过30 。
全部的测试数据满足：n<=10^4 且d<=20 。输入矩阵、向量中的元素均为整数，且绝对值均不超过 1000；

因此如果按照顺序计算，那么运算量超过10^9（约为1s），则会超时，因此可以在计算中合并一些运算。

二、代码展示（c）

#include 
int main() {
    int n,d;

    int i,j;
    scanf("%d%d",&n,&d);
    //printf("%d %d\n",n,d);
    //-------------------初始化-----------------------
    int** Q = (int**)malloc(sizeof(int*) * n);
    int** K = (int**)malloc(sizeof(int*) * n);
    int** V = (int**)malloc(sizeof(int*) * n);
    int* W = (int*)malloc(sizeof(int*) * n);
    //-------------------初始化-----------------------
    for(i = 0;i < n;i++){
        *(Q+i) = (int*)malloc(sizeof(int) * d);
        for(j = 0;j < d;j++){
            scanf("%d",&Q[i][j]);
        }
    }
    for(i = 0;i < n;i++){
        *(K+i) = (int*)malloc(sizeof(int) * d);
        for(j = 0;j < d;j++){
            scanf("%d",&K[i][j]);
        }
    }
    for(i = 0;i < n;i++){
        *(V+i) = (int*)malloc(sizeof(int) * d);
        for(j = 0;j < d;j++){
            scanf("%d",&V[i][j]);
        }
    }
    long long** res = (long long**)malloc(sizeof(long long*) * n);
    //long long** result = (long long**)malloc(sizeof(long long*) * n);
    for(i = 0;i < n;i++) {
        *(res+i) = (long long*)malloc(sizeof(long long) * n);
        //*(result+i) = (long long*)malloc(sizeof(long long) * d);
        scanf("%d",&W[i]);
    }


    for (i = 0;i < n;i++){
        for(j = 0;j < n;j++){
            res[i][j] = 0;
            int k,p;
            for(k = 0;k < d;k++) {
                //printf("%d %d\n",Q[i][k],K[j][k]);
                res[i][j] += (long long)Q[i][k]*(long long)K[j][k];
            }
        }
        for(j = 0;j < d;j++){
            long long result = 0;
            int k,p;
            for(k = 0;k < n;k++) {
                result += (long long)res[i][k]*(long long)V[k][j]*(long long)W[i];
            }
            printf("%lld ",result);
        }
        printf("\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

三、注意事项

此题因为存入的数很多，因此需要动态开辟二维数组。设一个二维数组为Q，方式如下：

int** Q = (int**)malloc(sizeof(int*) * n);
for(i = 0;i < n;i++){
        *(Q+i) = (int*)malloc(sizeof(int) * d);
        for(j = 0;j < d;j++){
            scanf("%d",&Q[i][j]);
        }
    }
1
2
3
4
5
6
7

边创建数组边读入会更省时间~