結果
問題 |
No.3003 多項式の割り算 〜hard〜
|
ユーザー |
|
提出日時 | 2025-01-17 21:36:58 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 1,046 bytes |
コンパイル時間 | 49 ms |
コンパイル使用メモリ | 8,064 KB |
実行使用メモリ | 12,928 KB |
最終ジャッジ日時 | 2025-01-17 21:37:13 |
合計ジャッジ時間 | 3,393 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
コンパイルメッセージ
Syntax OK
ソースコード
class Matrix attr_reader :n, :m, :rows def initialize(rows) @n, @m, @rows = rows.size, rows[0].size, rows end def self.id(n) new((0 ... n).map { |i| (0 ... n).map { |j| (i == j) ? 1 : 0 } }) end def [](i, j) @rows[i][j] end def +(other) self.class.new(@rows.map.with_index { |row, i| row.map.with_index { |x, j| (x + other[i, j]) } }) end def *(other) raise "dimension mismatch: #{@m} != #{other.n}" unless @m == other.n self.class.new((0 ... @n).map { |i| (0 ... other.m).map { |j| (0 ... @m).sum { |k| self[i, k] * other[k, j] } } }) 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 end A, B = gets.split.map(&:to_i) if B <= 1 xs = [0, 0] xs[B] = A b, a = xs puts "#{a} #{b}" exit end m = Matrix.new([ [-1, 1, 0], [-1, 0, 1], [0, 0, 0] ]) x = Matrix.new([ [A], [0], [0] ]) y = m**(B - 1) * x a, b = y[0, 0], y[1, 0] puts "#{a} #{b}"