結果

問題 No.1521 Playing Musical Chairs Alone
コンテスト
ユーザー yuruhiya
提出日時 2021-05-29 18:25:30
言語 Crystal
(1.14.0)
結果
AC  
実行時間 326 ms / 2,000 ms
コード長 4,286 bytes
コンパイル時間 18,167 ms
コンパイル使用メモリ 294,788 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 01:31:13
合計ジャッジ時間 19,298 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

# require "math/Mint"
macro static_modint(name, mod)
  struct {{name}}
    MOD = Int64.new({{mod}})

    def self.zero
      new
    end

    def self.raw(value : Int64)
      result = new
      result.value = value
      result
    end

    @value : Int64

    def initialize
      @value = 0i64
    end

    def initialize(value)
      @value = value.to_i64 % MOD
    end

    def initialize(m : self)
      @value = m.value
    end

    protected def value=(value : Int64)
      @value = value
    end

    getter value : Int64

    def + : self
      self
    end

    def - : self
      self.class.raw(value != 0 ? MOD &- value : 0i64)
    end

    def +(v)
      self + v.to_m
    end

    def +(m : self)
      x = value &+ m.value
      x &-= MOD if x >= MOD
      self.class.raw(x)
    end

    def -(v)
      self - v.to_m
    end

    def -(m : self)
      x = value &- m.value
      x &+= MOD if x < 0
      self.class.raw(x)
    end

    def *(v)
      self * v.to_m
    end

    def *(m : self)
      self.class.new(value &* m.value)
    end

    def /(v)
      self / v.to_m
    end

    def /(m : self)
      raise DivisionByZeroError.new if m.value == 0
      a, b, u, v = m.to_i64, MOD, 1i64, 0i64
      while b != 0
        t = a // b
        a &-= t &* b
        a, b = b, a
        u &-= t &* v
        u, v = v, u
      end
      self.class.new(value &* u)
    end

    def //(v)
      self / v
    end

    def **(exponent : Int)
      t, res = self, self.class.raw(1i64)
      while exponent > 0
        res *= t if exponent & 1 == 1
        t *= t
        exponent >>= 1
      end
      res
    end

    def ==(v)
      value == v
    end

    def ==(m : self)
      value == m.value
    end

    def succ
      self.class.raw(value != MOD &- 1 ? value &+ 1 : 0i64)
    end

    def pred
      self.class.raw(value != 0 ? value &- 1 : MOD &- 1)
    end

    def abs
      self
    end

    def to_i64 : Int64
      value
    end

    delegate to_s, to: @value
    delegate inspect, to: @value
  end

  struct Int
    def to_m : {{name}}
      {{name}}.new(self)
    end
  end

  class String
    def to_m : {{name}}
      {{name}}.new(self)
    end
  end
end

# require "math/Matrix"
class Matrix(T)
  include Indexable(Array(T))

  getter height : Int32
  getter width : Int32
  getter data : Array(Array(T))

  def Matrix.identity(size : Int32)
    result = Matrix(T).new(size, size)
    (0...size).each do |i|
      result[i][i] = T.new(1)
    end
    result
  end

  def initialize(@height, @width, init_value : T = T.zero)
    @data = Array(Array(T)).new(height) { Array(T).new(width, init_value) }
  end

  def initialize(init_matrix : Array(Array(T)))
    @height = init_matrix.size
    @width = init_matrix[0].size
    raise ArgumentError.new unless init_matrix.all? { |a| a.size == width }
    @data = init_matrix
  end

  delegate size, to: @data
  delegate unsafe_fetch, to: @data

  def +(other : self)
    IndexError.new unless height == other.height && width == other.width
    result = Matrix(T).new(height, width)
    (0...height).each do |i|
      (0...width).each do |j|
        result[i][j] = data[i][j] + other[i][j]
      end
    end
    result
  end

  def -(other : self)
    IndexError.new unless height == other.height && width == other.width
    result = Matrix(T).new(height, width)
    (0...height).each do |i|
      (0...width).each do |j|
        result[i][j] = data[i][j] - other[i][j]
      end
    end
    result
  end

  def *(other : self)
    IndexError.new unless width == other.height
    result = Matrix(T).new(height, other.width)
    (0...height).each do |i|
      (0...other.width).each do |j|
        (0...width).each do |k|
          result[i][j] += data[i][k] * other[k][j]
        end
      end
    end
    result
  end

  def **(k : Int)
    result = Matrix(T).identity(height)
    memo = Matrix.new(data)
    while k > 0
      result *= memo if k.odd?
      memo *= memo
      k >>= 1
    end
    result
  end

  def to_s(io)
    io << data
  end
end

static_modint(Mint, 10**9 + 7)

n, k, l = read_line.split.map(&.to_i)
a = Matrix(Mint).new(n, n)
(0...n).each do |i|
  (1..l).each do |ll|
    a[i][(i - ll) % n] = 1.to_m
  end
end
b = Matrix(Mint).new(n, 1)
b[0][0] = 1.to_m
puts (a ** k * b).join('\n', &.[0])
0