結果

問題 No.1340 おーじ君をさがせ
ユーザー maguroflymagurofly
提出日時 2021-01-19 23:27:59
言語 Ruby
(3.4.1)
結果
AC  
実行時間 190 ms / 2,000 ms
コード長 1,201 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 20,224 KB
最終ジャッジ日時 2024-12-17 19:54:16
合計ジャッジ時間 8,819 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
プレゼンテーションモードにする

class BitAndOrMatrix
attr_reader :n, :bits
def initialize(n, bits)
@n, @bits = n, bits
@u = (1 << n) - 1
@v = ((@u + 1)**n - 1) / @u
end
def self.rows(rows)
n, bits = rows.size, 0
rows.each_with_index do |row, i|
x = 0
row.each_with_index do |a, j|
x |= a << j
end
bits |= x << n * i
end
new(n, bits)
end
def self.id(n)
new(n, ((1 << (n + 1) * n) - 1) / ((1 << n + 1) - 1))
end
def [](i, j)
@bits >> i * @n + j & 1
end
def +(other)
self.class.new(@n, @bits | other.bits)
end
def *(other)
a, b = @bits, other.bits
bits = 0
while a > 0 and b > 0
bits |= ((a & @v) * @u) & ((b & @u) * @v)
a >>= 1
b >>= n
end
self.class.new(@n, bits)
end
def **(e)
r = self.class.id(@n)
x = self
while e > 0
r *= x if (e & 1) == 1
x *= x
e >>= 1
end
r
end
def to_a
(0 ... @n).map { |i| (0 ... @n).map { |j| self[i, j] } }
end
end
N, M, T = gets.split.map(&:to_i)
rows = Array.new(N) { [0] * N }
M.times do
a, b = gets.split.map(&:to_i)
rows[b][a] = 1
end
ans = BitAndOrMatrix.rows(rows) ** T
puts ans.to_a.transpose[0].sum
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0