ABC042D - いろはちゃんとマス目

問題

https://atcoder.jp/contests/abc042/tasks/arc058_b

回答1

defmodule Combination do
  @mod 1_000_000_007
  @max_index 200_000

  defp renew_table(table_name, initial_objects) do
    if :ets.info(table_name) != :undefined do
      :ets.delete(table_name)
    end

    :ets.new(table_name, [:set, :protected, :named_table])
    :ets.insert(table_name, initial_objects)
  end

  defp lookup(table_name, key) do
    [{_, value}] = :ets.lookup(table_name, key)
    value
  end

  def init do
    renew_table(:factorial, [{0, 1}, {1, 1}])
    renew_table(:inverse, [{1, 1}])
    renew_table(:factorial_inverse, [{0, 1}, {1, 1}])

    2..@max_index
    |> Enum.reduce(1, fn index, acc ->
      factorial = rem(acc * index, @mod)

      mod_inverse = lookup(:inverse, rem(@mod, index))
      inverse = @mod - rem(mod_inverse * div(@mod, index), @mod)

      pre_factorial_inverse = lookup(:factorial_inverse, index - 1)
      factorial_inverse = rem(pre_factorial_inverse * inverse, @mod)

      :ets.insert(:factorial, {index, factorial})
      :ets.insert(:inverse, {index, inverse})
      :ets.insert(:factorial_inverse, {index, factorial_inverse})

      factorial
    end)
  end

  def combination(n, r) do
    factorial_n = lookup(:factorial, n)
    factorial_inverse_nr = lookup(:factorial_inverse, n - r)
    factorial_inverse_r = lookup(:factorial_inverse, r)

    (factorial_inverse_nr * factorial_inverse_r)
    |> rem(@mod)
    |> Kernel.*(factorial_n)
    |> rem(@mod)
  end
end

Combination.init()

Combination.combination(6, 4)

defmodule Main do
  def main do
    :stdio
    |> IO.read(:all)
    |> solve()
    |> IO.puts()
  end

  defp split_words(words) do
    String.split(words, " ")
  end

  def solve(input) do
    [h, w, a, b] =
      input
      |> String.trim()
      |> split_words()
      |> Enum.map(&String.to_integer/1)

    Combination.init()

    0..(h - a - 1)
    |> Enum.reduce(0, fn h_i, acc ->
      l = Combination.combination(h_i + b - 1, h_i)
      r = Combination.combination(h + w - h_i - b - 2, h - 1 - h_i)
      acc + l * r
    end)
    |> rem(1_000_000_007)
  end
end

"""
2 3 1 1
"""
|> Main.solve()
|> then(&(&1 == 2))

"""
10 7 3 4
"""
|> Main.solve()
|> then(&(&1 == 3570))

"""
100000 100000 99999 99999
"""
|> Main.solve()
|> then(&(&1 == 1))

"""
100000 100000 44444 55555
"""
|> Main.solve()
|> then(&(&1 == 738_162_020))