結果

問題 No.1569 Nixoracci's Number
ユーザー flippergoflippergo
提出日時 2024-10-13 13:59:28
言語 Julia
(1.10.2)
結果
TLE  
実行時間 -
コード長 1,194 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 6,948 KB
実行使用メモリ 13,632 KB
最終ジャッジ日時 2024-10-13 13:59:41
合計ジャッジ時間 6,522 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

function matmul(X::Matrix{Int}, Y::Matrix{Int}, N::Int)
    Z = zeros(Int, N, N)
    for i in 1:N
        for j in 1:N
            for k in 1:N
                Z[i, j] = Z[i, j] ⊻ (X[i, k] * Y[k, j])  # XOR演算
            end
        end
    end
    return Z
end

function matpow(X::Matrix{Int}, k::Int, N::Int)
    I = Matrix{Int}(I, N, N)  # 単位行列を作成
    if k == 0
        return I
    elseif k == 1
        return X
    elseif k % 2 == 0
        half_pow = matpow(X, div(k, 2), N)
        return matmul(half_pow, half_pow, N)
    else
        half_pow = matpow(X, div(k - 1, 2), N)
        Y = matmul(half_pow, half_pow, N)
        return matmul(X, Y, N)
    end
end

function main()
    N, K = readline() |> split |> x -> map(parse, x)
    A = readline() |> split |> x -> map(parse, x)

    T = N + 1
    M = (K - 1) % T

    A1 = zeros(Int, N, N)

    # A1行列の初期化
    for i in 1:N-1
        A1[i, i + 1] = 1
    end
    for j in 1:N
        A1[N, j] = 1
    end

    # A1をM回累乗した行列を計算
    B = matpow(A1, M, N)

    # 答えを計算
    ans = 0
    for i in 1:N
        ans = ans ⊻ (B[1, i] * A[i])
    end

    println(ans)
end

main()
0