結果

問題 No.1340 おーじ君をさがせ
ユーザー maguroflymagurofly
提出日時 2021-01-19 23:24:04
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 1,228 bytes
コンパイル時間 453 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 19,968 KB
最終ジャッジ日時 2024-12-17 19:45:25
合計ジャッジ時間 8,933 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
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
#STDERR.puts ans.to_a.map(&:inspect)
puts ans.to_a[0].sum
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0