結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 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
ソースコード
class BitAndOrMatrixattr_reader :n, :bitsdef initialize(n, bits)@n, @bits = n, bits@u = (1 << n) - 1@v = ((@u + 1)**n - 1) / @uenddef self.rows(rows)n, bits = rows.size, 0rows.each_with_index do |row, i|x = 0row.each_with_index do |a, j|x |= a << jendbits |= x << n * iendnew(n, bits)enddef self.id(n)new(n, ((1 << (n + 1) * n) - 1) / ((1 << n + 1) - 1))enddef [](i, j)@bits >> i * @n + j & 1enddef +(other)self.class.new(@n, @bits | other.bits)enddef *(other)a, b = @bits, other.bitsbits = 0while a > 0 and b > 0bits ^= ((a & @v) * @u) & ((b & @u) * @v)a >>= 1b >>= nendself.class.new(@n, bits)enddef **(e)r = self.class.id(@n)x = selfwhile e > 0r *= x if (e & 1) == 1x *= xe >>= 1endrenddef to_a(0 ... @n).map { |i| (0 ... @n).map { |j| self[i, j] } }endendN, M, T = gets.split.map(&:to_i)rows = Array.new(N) { [0] * N }M.times doa, b = gets.split.map(&:to_i)rows[b][a] = 1endans = BitAndOrMatrix.rows(rows) ** T#STDERR.puts ans.to_a.map(&:inspect)puts ans.to_a[0].sum