CSP 202305-2 矩阵运算

黎 浩然/ 13 8 月, 2023/ 算法/ALGORITHMS/ 0 comments

试题编号：	202305-2
试题名称：	矩阵运算
时间限制：	5.0s
内存限制：	512.0MB

题目背景

问题描述

输入格式

输出格式

输出到标准输出中。

输出共 n 行，每行包含空格分隔的 d 个整数，表示计算的结果。

样例输入

3 2
1 2
3 4
5 6
10 10
-20 -20
30 30
6 5
4 3
2 1
4 0 -5

样例输出

480 240
0 0
-2200 -1100

子任务

70 的测试数据满足：n≤100 且 d≤10；输入矩阵、向量中的元素均为整数，且绝对值均不超过 30。

全部的测试数据满足：n ≤104 且 d≤20；输入矩阵、向量中的元素均为整数，且绝对值均不超过 1000。

提示

请谨慎评估矩阵乘法运算后的数值范围，并使用适当数据类型存储矩阵中的整数。

Java：100/100

需要先计算K^T * V矩阵，否则会内存超限。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int d = scanner.nextInt();

        int [][] Q = new int[n][d];
        long [][] K = new long[n][d];
        int [][] V = new int[n][d];
        int [] W = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d; j++) {
                Q[i][j] = scanner.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d; j++) {
                K[i][j] = scanner.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d; j++) {
                V[i][j] = scanner.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            W[i] = scanner.nextInt();
        }

        long [][] KTV = new long[d][d];
        for (int i = 0; i < d; i++) {
            for (int j = 0; j < d; j++) {
                for (int k = 0; k < n; k++) {
                    KTV[i][j] += K[k][i] * V[k][j];
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d; j++) {
                K[i][j] = 0;
                for (int k = 0; k < d; k++) {
                    K[i][j] += Q[i][k] * KTV[k][j];
                }
                K[i][j] *= W[i];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d; j++) {
                System.out.print(K[i][j]);
                if (j != d - 1) {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }
}