[python Python]白準10830次行列の平方を解く

質問する

問題は本当に簡単です.
与えられた行列のB二乗だけを要求すればよい.
言葉は簡単だが、入力は1000億に達する.
入力も大きく、平方なら分割征服で近づけるのでしょうか…?こんな想いで近づけば
さらに平方分征服を加えると、すべての問題が解決されると思います.
これはどこが間違っているのか悩ましい問題です...

に答える

で、1つ目は行列を乗算する関数です.

いずれにしても、マトリクスを乗算するには、マトリクスを乗算する関数を定義します.

def multiply(matrix1, matrix2):
    global n
    result = []
    for i in range(n):
        result2 = []
        for j in range(n):
            value = 0
            for t in range(n):
                value += matrix1[i][t] * matrix2[t][j]
            result2.append(value % 1000)
        result.append(result2)
    return result

マトリクスの総計算は(マトリクスサイズ)^3なので簡単(?)3つのforゲートで処理しましょう
あ、問題は残りの1000を1000で割るので、%1000を続けます.
(結果のみを…で割ると、数字が大きすぎて実行できません...)

の2番目は、反復二乗の関数を作成することです.

智秀は何度も二乗分割征服関数を使っていたので…!(フィボナッチを解いた時もそうでした)

def power(matrix, exponent):
    if exponent <= 1:
        return matrix
    else:
        if exponent % 2 == 0:
            new_exponent = power(matrix, exponent // 2)
            return multiply(new_exponent, new_exponent)
        else:
            new_exponent = power(matrix, exponent // 2)
            return multiply(multiply(new_exponent, new_exponent), matrix)

ただし、整数とは異なり、デフォルト値を行列として…!
そしてnew_exponentを計算するときに整数除算を書きます...
今は入力のみを受け入れ、関数に入れるだけでいいです.

しかし、80%の障害の中で、私は塞がれていました...、、
最後にテープを入力しました.
マトリクス要素が1000、Bが1の場合、残りの1000を出力する場合は0でなければなりません.
Bが1のとき、関数を呼び出さずにそのまま出力してしまい、1000はそのまま出てきたのでエラー…
とにかく、それを補うだけで、スムーズに完成することができます…!

コード#コード#

def multiply(matrix1, matrix2):
    global n
    result = []
    for i in range(n):
        result2 = []
        for j in range(n):
            value = 0
            for t in range(n):
                value += matrix1[i][t] * matrix2[t][j]
            result2.append(value % 1000)
        result.append(result2)
    return result


def power(matrix, exponent):
    if exponent <= 1:
        return matrix
    else:
        if exponent % 2 == 0:
            new_exponent = power(matrix, exponent // 2)
            return multiply(new_exponent, new_exponent)
        else:
            new_exponent = power(matrix, exponent // 2)
            return multiply(multiply(new_exponent, new_exponent), matrix)


n, k = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(n)]

if k == 1:
    for i in range(n):
        for j in range(n):
            mat[i][j] = mat[i][j] % 1000
    z = mat
else:
    z = power(mat, k)

for x in range(n):
    print(*z[x])

終わりだ!