#918673 (Fortran) No.2494 Sum within Components

• 問題: No.2494 Sum within Components
• ユーザー: osada-yum
• 提出日時: 2023-10-06 22:49:38
• 言語: Fortran (gFortran 13.2.0)
• 結果: AC
• 実行時間: 128 ms / 2,000 ms
• コード長: 12,183 bytes
• コンパイル時間: 727 ms
• コンパイル使用メモリ: 38,912 KB
• 実行使用メモリ: 7,564 KB
• 最終ジャッジ日時: 2024-07-26 16:47:33
• 合計ジャッジ時間: 2,434 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,812 KB
testcase_01	AC	1 ms; 6,944 KB
testcase_02	AC	1 ms; 6,944 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	1 ms; 6,944 KB
testcase_05	AC	1 ms; 6,944 KB
testcase_06	AC	1 ms; 6,940 KB
testcase_07	AC	1 ms; 6,940 KB
testcase_08	AC	1 ms; 6,940 KB
testcase_09	AC	12 ms; 6,944 KB
testcase_10	AC	11 ms; 6,944 KB
testcase_11	AC	4 ms; 6,940 KB
testcase_12	AC	17 ms; 6,940 KB
testcase_13	AC	9 ms; 6,940 KB
testcase_14	AC	112 ms; 6,944 KB
testcase_15	AC	123 ms; 6,940 KB
testcase_16	AC	47 ms; 6,944 KB
testcase_17	AC	46 ms; 7,564 KB
testcase_18	AC	53 ms; 7,564 KB
testcase_19	AC	128 ms; 7,436 KB

ソースコード

module union_find_m
  use, intrinsic :: iso_fortran_env
  implicit none
  type union_find
     integer(int32), allocatable :: par_(:), size_(:)
     integer(int32) :: setsize_
   contains
     procedure, pass :: init  => init_uf
     procedure, pass :: union => union_uf
     procedure, pass :: root  => root_uf
     procedure, pass :: same  => same_uf
     procedure, pass :: size  => size_uf
  end type union_find
contains
  subroutine init_uf(this, n)
    class(union_find), intent(inout) :: this
    integer(int32)   , intent(in)    :: n
    integer(int32)                   :: i
    if (allocated(this%par_)) then
       if (this%setsize_ /= n) then
          this%setsize_ = n
          block
            integer(int32), allocatable :: new_par(:), new_size(:)
            allocate(new_par(n), new_size(n))
            call move_alloc(from = new_par, to = this%par_)
            call move_alloc(from = new_size, to = this%size_)
          end block
       end if
    else
       this%setsize_ = n
       allocate(this%par_(n), this%size_(n))
    end if
    this%par_(:)  = [(i, i = 1, n)]
    this%size_(:) = 1
  end subroutine init_uf
  subroutine union_uf(this, i, j)
    class(union_find), intent(inout) :: this
    integer(int32)   , intent(in)    :: i, j
    integer(int32) :: x, y
    x = this%root(i)
    y = this%root(j)
    if (x == y) return
    if (this%size_(x) < this%size_(y)) then
       this%par_(x) = y
       this%size_(y) = this%size_(x) + this%size_(y)
    else
       this%par_(y) = x
       this%size_(x) = this%size_(x) + this%size_(y)
    end if
  end subroutine union_uf
  impure recursive integer(int32) function root_uf(this, i) result(res)
    class(union_find), intent(inout) :: this
    integer(int32)   , intent(in) :: i
    res = i
    if (this%par_(res) == res) return
    this%par_(res) = this%root(this%par_(res))
    res = this%par_(res)
  end function root_uf
  impure logical function same_uf(this, i, j)
    class(union_find), intent(inout) :: this
    integer(int32)   , intent(in) :: i, j
    same_uf = this%root(i) == this%root(j)
  end function same_uf
  impure integer(int32) function size_uf(this, i) result(res)
    class(union_find), intent(inout) :: this
    integer(int32), intent(in) :: i
    integer(int32) :: root
    root = this%root(i)
    res = this%size_(root)
  end function size_uf
end module union_find_m

module modint_m
  use, intrinsic :: iso_fortran_env
  implicit none
  private
  integer(int64), parameter :: modulo = 998244353
  public :: modint
  public :: assignment(=), operator(+), operator(-), operator(*), operator(/), inv, operator(**), combination
  type :: modint
     integer(int64) :: val_
   contains
     procedure, pass :: to_i64 => to_i64_modint
  end type modint
  interface modint
     module procedure :: init_modint_i32, init_modint_i64
  end interface modint
  interface assignment(=)
     module procedure :: assign_m_from_m, assign_m_from_i32, assign_m_from_i64
  end interface assignment(=)
  interface operator(+)
     module procedure :: add_m_m, add_i32_m, add_i64_m, add_m_i32, add_m_i64
  end interface operator(+)
  interface operator(-)
     module procedure :: sub_m_m, sub_i32_m, sub_i64_m, sub_m_i32, sub_m_i64
  end interface operator(-)
  interface operator(*)
     module procedure :: mul_m_m, mul_i32_m, mul_i64_m, mul_m_i32, mul_m_i64
  end interface operator(*)
  interface inv
     module procedure :: inv_modint, inv_i32, inv_i64
  end interface inv
  interface operator(/)
     module procedure :: div_m_m, div_i32_m, div_i64_m, div_m_i32, div_m_i64
  end interface operator(/)
  interface operator(**)
     module procedure :: pow_m_i32, pow_m_i64
  end interface operator(**)
  interface combination
     module procedure :: combination_m_m, combination_m_i32, combination_m_i64, combination_i32_m, combination_i64_m
  end interface combination
contains
  pure integer(int64) function to_i64_modint(mx) result(res)
    class(modint), intent(in) :: mx
    res = mx%val_
  end function to_i64_modint
  pure elemental type(modint) function init_modint_i32(x) result(res)
    integer(int32), intent(in) :: x
    res = modint(int(x, int64))
  end function init_modint_i32
  pure elemental type(modint) function init_modint_i64(x) result(res)
    integer(int64), intent(in) :: x
    res%val_ = mod(x, modulo)
    if (res%val_ < 0) res%val_ = res%val_ + modulo
  end function init_modint_i64
  pure subroutine assign_m_from_m(this, x)
    type(modint), intent(out) :: this
    type(modint), intent(in) :: x
    this%val_ = x%val_
  end subroutine assign_m_from_m
  pure subroutine assign_m_from_i32(this, x)
    type(modint), intent(out) :: this
    integer(int32), intent(in) :: x
    this = modint(x)
  end subroutine assign_m_from_i32
  pure subroutine assign_m_from_i64(this, x)
    type(modint), intent(out) :: this
    integer(int64), intent(in) :: x
    this = modint(x)
  end subroutine assign_m_from_i64
  pure type(modint) function add_m_m(mx, my) result(res)
    type(modint), intent(in) :: mx, my
    res%val_ = mod(mx%val_ + my%val_, modulo)
  end function add_m_m
  pure type(modint) function add_i32_m(x, my) result(res)
    integer(int32), intent(in) :: x
    type(modint), intent(in) :: my
    res = int(x, int64) + my
  end function add_i32_m
  pure type(modint) function add_i64_m(x, my) result(res)
    integer(int64), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) + my
  end function add_i64_m
  pure type(modint) function add_m_i32(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int32), intent(in) :: y
    res = mx + modint(y)
  end function add_m_i32
  pure type(modint) function add_m_i64(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int64), intent(in) :: y
    res = mx + modint(y)
  end function add_m_i64
  pure type(modint) function sub_m_m(mx, my) result(res)
    type(modint), intent(in) :: mx, my
    res%val_ = mod(mx%val_ - my%val_, modulo)
    if (res%val_ < 0) res%val_ = res%val_ + modulo
  end function sub_m_m
  pure type(modint) function sub_i32_m(x, my) result(res)
    integer(int32), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) - my
  end function sub_i32_m
  pure type(modint) function sub_i64_m(x, my) result(res)
    integer(int64), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) - my
  end function sub_i64_m
  pure type(modint) function sub_m_i32(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int32), intent(in) :: y
    res = mx - modint(y)
  end function sub_m_i32
  pure type(modint) function sub_m_i64(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int64), intent(in) :: y
    res = mx - modint(y)
  end function sub_m_i64
  pure type(modint) function mul_m_m(mx, my) result(res)
    type(modint), intent(in) :: mx, my
    res%val_ = mod(mx%val_ * my%val_, modulo)
  end function mul_m_m
  pure type(modint) function mul_i32_m(x, my) result(res)
    integer(int32), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) * my
  end function mul_i32_m
  pure type(modint) function mul_i64_m(x, my) result(res)
    integer(int64), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) * my
  end function mul_i64_m
  pure type(modint) function mul_m_i32(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int32), intent(in) :: y
    res = mx * modint(y)
  end function mul_m_i32
  pure type(modint) function mul_m_i64(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int64), intent(in) :: y
    res = mx * modint(y)
  end function mul_m_i64

  pure type(modint) function inv_modint(mx) result(res)
    type(modint), intent(in) :: mx
    integer(int64) :: g, a_inv, y
    call extend_euclid(mx%val_, modulo, g, a_inv, y)
    !> if (g /= 1) error stop 1, something wrong...
    !> g == 1.
    res = modint(a_inv)
  end function inv_modint
  pure type(modint) function inv_i32(x) result(res)
    integer(int32), intent(in) :: x
    res = inv_modint(modint(x))
  end function inv_i32
  pure type(modint) function inv_i64(x) result(res)
    integer(int64), intent(in) :: x
    res = inv_modint(modint(x))
  end function inv_i64
  !> a*x + b*y == g
  pure subroutine extend_euclid(a, b, g, x, y)
    integer(int64), intent(in)  :: a, b
    integer(int64), intent(out) :: g, x, y
    integer(int64) :: q
    integer(int64) :: zs(0:1), xs(0:1), ys(0:1)
    integer(int32) :: old, next
    zs(0) = a; zs(1) = b
    xs(0) = 1; xs(1) = 0
    ys(0) = 0; ys(1) = 1
    old = 1
    do
       next = ieor(old, 1)
       if (zs(old) == 0) exit
       q = zs(next) / zs(old)
       zs(next) = zs(next) - q*zs(old)
       xs(next) = xs(next) - q*xs(old)
       ys(next) = ys(next) - q*ys(old)
       old = next
    end do
    x = xs(next)
    y = ys(next)
    g = a*x + b*y
  end subroutine extend_euclid

  pure type(modint) function div_m_m(mx, my) result(res)
    type(modint), intent(in) :: mx, my
    res = mx * inv(my)
  end function div_m_m
  pure type(modint) function div_i32_m(x, my) result(res)
    integer(int32), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) / my
  end function div_i32_m
  pure type(modint) function div_i64_m(x, my) result(res)
    integer(int64), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) / my
  end function div_i64_m
  pure type(modint) function div_m_i32(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int32), intent(in) :: y
    res = mx / modint(y)
  end function div_m_i32
  pure type(modint) function div_m_i64(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int64), intent(in) :: y
    res = mx / modint(y)
  end function div_m_i64

  pure type(modint) function pow_m_i32(mx, p) result(res)
    type(modint), intent(in) :: mx
    integer(int32), intent(in) :: p
    res = mx ** int(p, int64)
  end function pow_m_i32
  pure type(modint) function pow_m_i64(mx, p) result(res)
    type(modint), intent(in) :: mx
    integer(int64), intent(in) :: p
    type(modint) :: mv, mx_powered
    integer(int64) :: pow
    mv = 1
    mx_powered = mx
    pow = p
    do while (pow /= 0)
       if (iand(pow, b'1') == 1) then
          mv = mv * mx_powered
       end if
       mx_powered = mx_powered * mx_powered
       pow = ishft(pow, -1)
    end do
    res = mv
  end function pow_m_i64
  pure type(modint) function combination_m_m(mn, mr) result(res)
    type(modint), intent(in) :: mn, mr
    integer(int64) :: i
    res = modint(1)
    do i = 1, mr%to_i64()
       res = res * (mn%to_i64()-i+1) / i
    end do
  end function combination_m_m
  pure type(modint) function combination_m_i32(mn, r) result(res)
    type(modint), intent(in) :: mn
    integer(int32), intent(in) :: r
    res = combination(mn, modint(r))
  end function combination_m_i32
  pure type(modint) function combination_m_i64(mn, r) result(res)
    type(modint), intent(in) :: mn
    integer(int64), intent(in) :: r
    res = combination(mn, modint(r))
  end function combination_m_i64
  pure type(modint) function combination_i32_m(n, mr) result(res)
    integer(int32), intent(in) :: n
    type(modint), intent(in) :: mr
    res = combination(modint(n), mr)
  end function combination_i32_m
  pure type(modint) function combination_i64_m(n, mr) result(res)
    integer(int64), intent(in) :: n
    type(modint), intent(in) :: mr
    res = combination(modint(n), mr)
  end function combination_i64_m
end module modint_m

program yukicoder_2494
  use, intrinsic :: iso_fortran_env
  use union_find_m
  use modint_m
  implicit none
  integer(int32) :: n, m, u, v
  integer(int64), allocatable :: arr(:)
  type(modint) :: ans
  type(modint), allocatable :: summ(:)
  type(union_find) :: uf
  integer(int32) :: i
  read(input_unit, *) n, m
  allocate(arr(n))
  read(input_unit, *) arr(:)
  call uf%init(n)
  do i = 1, m
     read(input_unit, *) u, v
     call uf%union(u, v)
  end do
  allocate(summ(n), source = modint(0))
  ans = modint(1)
  do i = 1, n
     summ(uf%root(i)) = summ(uf%root(i)) + arr(i)
  end do
  do i = 1, n
     ans = ans * summ(uf%root(i))
  end do
  write(output_unit, '(i0)') ans
end program yukicoder_2494