CSP题解 矩阵运算

CSP题解 矩阵运算

CCF对CSP历次认证真题拥有版权，所以不放题目了。我的代码记一下。

http://118.190.20.162/view.page?gpid=T169

有提示：请谨慎评估矩阵乘法运算后的数值范围，不会是大整数吧，直接python好了，这玩意儿要是能import torch就无敌了

本质就是手写矩阵乘法，转置，结果70分：

def pxq(p, q):
    # p:        n*d
    # q:        d*m
    # result:    n*m
    n = len(p)
    d = len(q)
    m = len(q[0])
    L = [[0 for __ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            row = p[i]
            col = [q[t][j] for t in range(d)]
            L[i][j] = sum([row[t] * col[t] for t in range(d)])
    return L

def T(L):
    # L: p*q
    # res: q*p
    p = len(L)
    q = len(L[0])
    res = [[L[j][i] for j in range(p)] for i in range(q)]
    return res

n, d = map(int, input().split())

Q = []
for i in range(n):
    Q.append(list(map(int, input().split())))

K = []
for i in range(n):
    K.append(list(map(int, input().split())))

V = []
for i in range(n):
    V.append(list(map(int, input().split())))

W = list(map(int, input().split()))

kt = T(K)
qxkt = pxq(Q, kt)
wqxkt = [[t * W[i] for t in qxkt[i]] for i in range(len(W))]
final = pxq(wqxkt, V)

for i in final:
    print(" ".join(str(j) for j in i))

思考：得分70数据范围是$n\le100,d\le10$，另外30分的数据范围是$n\le10^{4},d\le20$，其中$n$数量级猛增，d变化不大，是不是和复杂度有关系。注意到，上面代码中间过程出现了$n*n$的庞大矩阵：

kt = T(K)  # kt: d*n
qxkt = pxq(Q, kt)  # n*d d*n = n*n
wqxkt = [[t * W[i] for t in qxkt[i]] for i in range(len(W))]  # n*n
final = pxq(wqxkt, V)  # n*n n*d = n*d

#Q Kt V : n*d d*n n*d

先算$Kt \times V$好了：

kt = T(K) 
ktv = pxq(kt, V)  
qktv = pxq(Q, ktv)
final = [[t * W[i] for t in qktv[i]] for i in range(len(W))]

时间ok，空间使用大大减少。