結果

問題 No.1749 ラムドスウイルスの感染拡大
ユーザー tamura2004tamura2004
提出日時 2021-11-20 16:57:03
言語 Crystal
(1.11.2)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 4,518 bytes
コンパイル時間 24,131 ms
コンパイル使用メモリ 260,440 KB
実行使用メモリ 15,536 KB
最終ジャッジ日時 2023-09-02 12:21:15
合計ジャッジ時間 25,184 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge16
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
12,308 KB
testcase_01 AC 6 ms
12,208 KB
testcase_02 AC 5 ms
12,340 KB
testcase_03 AC 5 ms
12,216 KB
testcase_04 AC 16 ms
12,692 KB
testcase_05 AC 6 ms
12,260 KB
testcase_06 AC 6 ms
12,332 KB
testcase_07 AC 5 ms
12,396 KB
testcase_08 AC 6 ms
12,176 KB
testcase_09 AC 6 ms
12,284 KB
testcase_10 AC 12 ms
15,296 KB
testcase_11 AC 12 ms
15,312 KB
testcase_12 AC 22 ms
15,240 KB
testcase_13 AC 7 ms
12,208 KB
testcase_14 AC 7 ms
12,488 KB
testcase_15 AC 9 ms
12,420 KB
testcase_16 AC 10 ms
12,524 KB
testcase_17 AC 20 ms
15,536 KB
testcase_18 AC 24 ms
15,336 KB
testcase_19 AC 23 ms
15,252 KB
testcase_20 AC 6 ms
12,480 KB
testcase_21 AC 6 ms
12,504 KB
testcase_22 AC 5 ms
12,236 KB
testcase_23 AC 5 ms
12,196 KB
testcase_24 AC 6 ms
12,172 KB
testcase_25 AC 11 ms
15,416 KB
testcase_26 AC 8 ms
13,912 KB
testcase_27 AC 7 ms
13,060 KB
testcase_28 AC 16 ms
12,540 KB
testcase_29 AC 15 ms
12,656 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# require "crystal/graph"
# 重みなしグラフ
alias V = Int32

class Graph
  getter n : Int32
  getter g : Array(Array(Int32))
  delegate "[]", to: g

  def initialize(@n, @g)
  end

  def initialize(n)
    @n = n.to_i
    @g = Array.new(n) { [] of Int32 }
  end

  def initialize(n, m)
    initialize(n)
    m.times do |i|
      yield self, i
    end
  end

  def read
    v, nv = gets.to_s.split.map(&.to_i64)
    add v, nv
  end

  # vからnvに辺を追加する
  #
  # origin : 0-indexed or 1-indexed
  # both : 無向グラフ、有向グラフ
  def add(v, nv, origin = 1, both = true)
    v = v.to_i - origin
    nv = nv.to_i - origin
    g[v] << nv
    g[nv] << v if both
  end

  def bfs(root = 0)
    seen = Array.new(n, false)
    seen[root] = true
    q = Deque.new([root])
    while q.size > 0
      v = q.shift
      g[v].each do |nv|
        next if seen[nv]
        seen[nv] = true
        yield v, nv
        q << nv
      end
    end
  end

  # 連結成分に分解
  #
  # ```
  # g = Graph.new(4)
  # g.add 1, 2
  # g.add 3, 4
  # g.decomposit_connected_element # => {[0,1,0,1],[[0,1],[2,3]]
  # ```
  def decomposit_connected_element
    seen = Array.new(n, false)

    ix = [-1] * n
    conn = [] of Array(Int32)

    n.times do |iv|
      next if seen[iv]
      seen[iv] = true

      ix[iv] = 0
      con = [iv]
      q = Deque.new([iv])

      while q.size > 0
        v = q.shift
        g[v].each do |nv|
          next if seen[nv]
          seen[nv] = true

          ix[nv] = con.size
          con << nv
          q << nv
        end
      end
      conn << con
    end
    return {ix, conn}
  end

  # デバッグ用：アスキーアートで可視化
  def debug(origin = 1, di = true)
    case n
    when 0
      puts "++"
      puts "++"
      return
    when 1
      puts "+---+"
      puts "| #{origin} |"
      puts "+---+"
      return
    end

    if di
      File.open("debug.dot", "w") do |fh|
        fh.puts "digraph tree {"
        n.times do |v|
          g[v].each do |nv|
            next if v >= nv
            fh.puts "  #{v + origin} -- #{nv + origin};"
          end
        end
        fh.puts "}"
      end
      puts `cat debug.dot | graph-easy --from=dot --as_ascii`
    else
      File.open("debug.dot", "w") do |fh|
        fh.puts "graph tree {"
        n.times do |v|
          g[v].each do |nv|
            # next if v >= nv
            fh.puts "  #{v + origin} -> #{nv + origin};"
          end
        end
        fh.puts "}"
      end
      puts `cat debug.dot | graph-easy --from=dot --as_ascii`
    end
  end
end


# require "crystal/modint9"
# modint
struct ModInt
  MAX   = 1_000_000
  MOD = 998_244_353_i64

  class_getter f = Array(ModInt).new(MAX)
  getter v : Int64

  def self.f(n)
    f << 1.to_m if f.empty?
    f.size.upto(n) do |i|
      f << f.last * i
    end
    f[n]
  end

  def self.p(n, k)
    return ModInt.zero if n < k
    return ModInt.zero if k < 0
    n.f // (n - k).f
  end

  def self.c(n, k)
    return ModInt.zero if n < k
    return ModInt.zero if k < 0
    if n <= MAX
      p(n, k) // k.f
    else
      ans = 1.to_m
      (1..k).each do |i|
        ans *= (n + 1 - i)
        ans //= i
      end
      ans
    end
  end

  def self.h(n, k)
    c(n + k - 1, k)
  end

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

  {% for op in %w(+ - *) %}
    def {{op.id}}(b)
      ModInt.new(v {{op.id}} (b.to_i64 % MOD))
    end
  {% end %}

  def **(b)
    a = self
    ans = 1.to_m
    while b > 0
      ans *= a if b.odd?
      b //= 2
      a *= a
    end
    return ans
  end

  def inv
    self ** (MOD - 2)
  end

  def //(b)
    self * b.to_m.inv
  end

  def self.zero
    new(0)
  end

  def ==(b)
    v == b.to_i64
  end

  def to_m
    self
  end

  delegate to_i64, to: v
  delegate to_s, to: v
  delegate inspect, to: v
end

struct Int
  def to_m
    ModInt.new(to_i64)
  end

  def f
    ModInt.f(self)
  end

  def p(k)
    ModInt.p(self, k)
  end

  def c(k)
    ModInt.c(self, k)
  end

  def h(k)
    ModInt.h(self, k)
  end
end

module Enumerable(T)
  def product(initial : ModInt)
    reduce(initial) { |memo, e| memo * e }
  end
end


n, m, t = gets.to_s.split.map(&.to_i)
g = Graph.new(n)
m.times do
  v, nv = gets.to_s.split.map(&.to_i)
  g.add v, nv, origin: 0
end
# g.debug

ans = Array.new(n) { 0.to_m }
ans[0] = 1.to_m

t.times do
  cnt = Array.new(n) { 0.to_m }
  n.times do |v|
    g[v].each do |nv|
      cnt[v] += ans[nv]
    end
  end
  n.times { |i| ans[i] = cnt[i] }
end

pp ans[0]
0