結果

問題 No.1569 Nixoracci's Number
コンテスト
ユーザー flippergo
提出日時 2024-10-13 13:59:28
言語 Julia
(2.11.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1 -- * 2
other -- * 21
権限があれば一括ダウンロードができます

ソースコード

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