P16668 [CSPro 30] Matrix Operations

The testdata on Luogu is for non-official communication only and is not official testdata. Official judging link: 。

$\text{Softmax}(\frac{Q \times K^T}{\sqrt{d}}) \times V$ is the core expression of the attention module in Transformers, where $Q$, $K$, and $V$ are all matrices with $n$ rows and $d$ columns, $K^T$ denotes the transpose of matrix $K$, and $\times$ denotes matrix multiplication. To make computation easier, student Dundun simplifies Softmax into an element-wise multiplication by a one-dimensional vector $W$ of length $n$: $$ (W \cdot (Q \times K^T)) \times V $$ Element-wise multiplication here means multiplying corresponding positions. Let $W^{(i)}$ be the $i$-th element of vector $W$. That is, every element in the $i$-th row of $(Q \times K^T)$ is multiplied by $W^{(i)}$. Given matrices $Q$, $K$, and $V$, and vector $W$, compute the result produced by Dundun using the simplified formula.

Read input from standard input. The first line contains two positive integers $n$ and $d$ separated by spaces, representing the size of the matrices. Then matrices $Q$, $K$, and $V$ are given in order. Each matrix is given in $n$ lines, and each line contains $d$ integers separated by spaces. The $j$-th number in the $i$-th line corresponds to the element in row $i$ and column $j$ of the matrix. The last line contains $n$ integers, representing vector $W$.

Write output to standard output. Output $n$ lines in total, each containing $d$ integers separated by spaces, representing the computed result.

### Subtasks $70\%$ of the testdata satisfies: $n \le 100$ and $d \le 10$; all elements in the input matrices and vectors are integers, and their absolute values do not exceed $30$. All testdata satisfies: $n \le 10^4$ and $d \le 20$; all elements in the input matrices and vectors are integers, and their absolute values do not exceed $1000$. ### Hint Please carefully estimate the value range after matrix multiplication, and use an appropriate data type to store the integers in the matrices. Translated by ChatGPT 5