結果

問題 No.1340 おーじ君をさがせ
ユーザー magurofly
提出日時 2021-01-19 15:43:19
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 906 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 29,312 KB
最終ジャッジ日時 2024-12-16 10:36:40
合計ジャッジ時間 99,473 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 4 TLE * 31
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class BitAndOrSquareMatrix
    attr_reader :rows, :n
    def initialize(*rows)
        @rows, @n = rows, rows.size
    end
    
    def [](i, j)
        @rows[i][j]
    end
    
    def *(other)
        BitAndOrSquareMatrix.new(*(0 ... @n).map { |i|
            (0 ... @n).map { |j|
                (0 ... @n).inject(0) { |prod, k| prod | self[i, k] & other[k, j] }
            }
        })
    end
    
    def **(e)
        x = self
        r = BitAndOrSquareMatrix.new(*(0 ... @n).map { |i| (0 ... @n).map { |j| (i == j) ? 1 : 0 } })
        while e > 0
            r *= x if e.odd?
            x *= x
            e >>= 1
        end
        r
    end
end

N, M, T = gets.split.map(&:to_i)
rows = Array.new(N) { [0] * N }
M.times do
    a, b = gets.split.map { |s| s.to_i - 1 }
    rows[b][a] = 1
end
matrix = BitAndOrSquareMatrix.new(*rows)
result = matrix ** T

puts (0 ... N).sum { |i| result[i, 0] }
0