結果
| 問題 | No.2494 Sum within Components |
| ユーザー |
 osada-yum
|
| 提出日時 | 2023-10-06 22:49:38 |
| 言語 | Fortran (gFortran 13.2.0) |
| 結果 |
AC
|
| 実行時間 | 168 ms / 2,000 ms |
| コード長 | 12,183 bytes |
| コンパイル時間 | 1,383 ms |
| コンパイル使用メモリ | 33,672 KB |
| 実行使用メモリ | 7,376 KB |
| 最終ジャッジ日時 | 2023-10-06 22:49:41 |
| 合計ジャッジ時間 | 2,642 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 1 ms
4,380 KB |
| testcase_03 | AC | 1 ms
4,384 KB |
| testcase_04 | AC | 1 ms
4,376 KB |
| testcase_05 | AC | 1 ms
4,380 KB |
| testcase_06 | AC | 1 ms
4,380 KB |
| testcase_07 | AC | 1 ms
4,380 KB |
| testcase_08 | AC | 1 ms
4,380 KB |
| testcase_09 | AC | 12 ms
4,376 KB |
| testcase_10 | AC | 12 ms
4,380 KB |
| testcase_11 | AC | 5 ms
4,380 KB |
| testcase_12 | AC | 19 ms
4,380 KB |
| testcase_13 | AC | 12 ms
4,380 KB |
| testcase_14 | AC | 143 ms
5,804 KB |
| testcase_15 | AC | 154 ms
5,112 KB |
| testcase_16 | AC | 63 ms
5,720 KB |
| testcase_17 | AC | 66 ms
7,376 KB |
| testcase_18 | AC | 72 ms
7,348 KB |
| testcase_19 | AC | 168 ms
7,340 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