結果
問題 | No.2494 Sum within Components |
ユーザー |
|
提出日時 | 2023-10-06 22:49:38 |
言語 | Fortran (gFortran 14.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
module union_find_muse, intrinsic :: iso_fortran_envimplicit nonetype union_findinteger(int32), allocatable :: par_(:), size_(:)integer(int32) :: setsize_containsprocedure, pass :: init => init_ufprocedure, pass :: union => union_ufprocedure, pass :: root => root_ufprocedure, pass :: same => same_ufprocedure, pass :: size => size_ufend type union_findcontainssubroutine init_uf(this, n)class(union_find), intent(inout) :: thisinteger(int32) , intent(in) :: ninteger(int32) :: iif (allocated(this%par_)) thenif (this%setsize_ /= n) thenthis%setsize_ = nblockinteger(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 blockend ifelsethis%setsize_ = nallocate(this%par_(n), this%size_(n))end ifthis%par_(:) = [(i, i = 1, n)]this%size_(:) = 1end subroutine init_ufsubroutine union_uf(this, i, j)class(union_find), intent(inout) :: thisinteger(int32) , intent(in) :: i, jinteger(int32) :: x, yx = this%root(i)y = this%root(j)if (x == y) returnif (this%size_(x) < this%size_(y)) thenthis%par_(x) = ythis%size_(y) = this%size_(x) + this%size_(y)elsethis%par_(y) = xthis%size_(x) = this%size_(x) + this%size_(y)end ifend subroutine union_ufimpure recursive integer(int32) function root_uf(this, i) result(res)class(union_find), intent(inout) :: thisinteger(int32) , intent(in) :: ires = iif (this%par_(res) == res) returnthis%par_(res) = this%root(this%par_(res))res = this%par_(res)end function root_ufimpure logical function same_uf(this, i, j)class(union_find), intent(inout) :: thisinteger(int32) , intent(in) :: i, jsame_uf = this%root(i) == this%root(j)end function same_ufimpure integer(int32) function size_uf(this, i) result(res)class(union_find), intent(inout) :: thisinteger(int32), intent(in) :: iinteger(int32) :: rootroot = this%root(i)res = this%size_(root)end function size_ufend module union_find_mmodule modint_muse, intrinsic :: iso_fortran_envimplicit noneprivateinteger(int64), parameter :: modulo = 998244353public :: modintpublic :: assignment(=), operator(+), operator(-), operator(*), operator(/), inv, operator(**), combinationtype :: modintinteger(int64) :: val_containsprocedure, pass :: to_i64 => to_i64_modintend type modintinterface modintmodule procedure :: init_modint_i32, init_modint_i64end interface modintinterface assignment(=)module procedure :: assign_m_from_m, assign_m_from_i32, assign_m_from_i64end interface assignment(=)interface operator(+)module procedure :: add_m_m, add_i32_m, add_i64_m, add_m_i32, add_m_i64end interface operator(+)interface operator(-)module procedure :: sub_m_m, sub_i32_m, sub_i64_m, sub_m_i32, sub_m_i64end interface operator(-)interface operator(*)module procedure :: mul_m_m, mul_i32_m, mul_i64_m, mul_m_i32, mul_m_i64end interface operator(*)interface invmodule procedure :: inv_modint, inv_i32, inv_i64end interface invinterface operator(/)module procedure :: div_m_m, div_i32_m, div_i64_m, div_m_i32, div_m_i64end interface operator(/)interface operator(**)module procedure :: pow_m_i32, pow_m_i64end interface operator(**)interface combinationmodule procedure :: combination_m_m, combination_m_i32, combination_m_i64, combination_i32_m, combination_i64_mend interface combinationcontainspure integer(int64) function to_i64_modint(mx) result(res)class(modint), intent(in) :: mxres = mx%val_end function to_i64_modintpure elemental type(modint) function init_modint_i32(x) result(res)integer(int32), intent(in) :: xres = modint(int(x, int64))end function init_modint_i32pure elemental type(modint) function init_modint_i64(x) result(res)integer(int64), intent(in) :: xres%val_ = mod(x, modulo)if (res%val_ < 0) res%val_ = res%val_ + moduloend function init_modint_i64pure subroutine assign_m_from_m(this, x)type(modint), intent(out) :: thistype(modint), intent(in) :: xthis%val_ = x%val_end subroutine assign_m_from_mpure subroutine assign_m_from_i32(this, x)type(modint), intent(out) :: thisinteger(int32), intent(in) :: xthis = modint(x)end subroutine assign_m_from_i32pure subroutine assign_m_from_i64(this, x)type(modint), intent(out) :: thisinteger(int64), intent(in) :: xthis = modint(x)end subroutine assign_m_from_i64pure type(modint) function add_m_m(mx, my) result(res)type(modint), intent(in) :: mx, myres%val_ = mod(mx%val_ + my%val_, modulo)end function add_m_mpure type(modint) function add_i32_m(x, my) result(res)integer(int32), intent(in) :: xtype(modint), intent(in) :: myres = int(x, int64) + myend function add_i32_mpure type(modint) function add_i64_m(x, my) result(res)integer(int64), intent(in) :: xtype(modint), intent(in) :: myres = modint(x) + myend function add_i64_mpure type(modint) function add_m_i32(mx, y) result(res)type(modint), intent(in) :: mxinteger(int32), intent(in) :: yres = mx + modint(y)end function add_m_i32pure type(modint) function add_m_i64(mx, y) result(res)type(modint), intent(in) :: mxinteger(int64), intent(in) :: yres = mx + modint(y)end function add_m_i64pure type(modint) function sub_m_m(mx, my) result(res)type(modint), intent(in) :: mx, myres%val_ = mod(mx%val_ - my%val_, modulo)if (res%val_ < 0) res%val_ = res%val_ + moduloend function sub_m_mpure type(modint) function sub_i32_m(x, my) result(res)integer(int32), intent(in) :: xtype(modint), intent(in) :: myres = modint(x) - myend function sub_i32_mpure type(modint) function sub_i64_m(x, my) result(res)integer(int64), intent(in) :: xtype(modint), intent(in) :: myres = modint(x) - myend function sub_i64_mpure type(modint) function sub_m_i32(mx, y) result(res)type(modint), intent(in) :: mxinteger(int32), intent(in) :: yres = mx - modint(y)end function sub_m_i32pure type(modint) function sub_m_i64(mx, y) result(res)type(modint), intent(in) :: mxinteger(int64), intent(in) :: yres = mx - modint(y)end function sub_m_i64pure type(modint) function mul_m_m(mx, my) result(res)type(modint), intent(in) :: mx, myres%val_ = mod(mx%val_ * my%val_, modulo)end function mul_m_mpure type(modint) function mul_i32_m(x, my) result(res)integer(int32), intent(in) :: xtype(modint), intent(in) :: myres = modint(x) * myend function mul_i32_mpure type(modint) function mul_i64_m(x, my) result(res)integer(int64), intent(in) :: xtype(modint), intent(in) :: myres = modint(x) * myend function mul_i64_mpure type(modint) function mul_m_i32(mx, y) result(res)type(modint), intent(in) :: mxinteger(int32), intent(in) :: yres = mx * modint(y)end function mul_m_i32pure type(modint) function mul_m_i64(mx, y) result(res)type(modint), intent(in) :: mxinteger(int64), intent(in) :: yres = mx * modint(y)end function mul_m_i64pure type(modint) function inv_modint(mx) result(res)type(modint), intent(in) :: mxinteger(int64) :: g, a_inv, ycall 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_modintpure type(modint) function inv_i32(x) result(res)integer(int32), intent(in) :: xres = inv_modint(modint(x))end function inv_i32pure type(modint) function inv_i64(x) result(res)integer(int64), intent(in) :: xres = inv_modint(modint(x))end function inv_i64!> a*x + b*y == gpure subroutine extend_euclid(a, b, g, x, y)integer(int64), intent(in) :: a, binteger(int64), intent(out) :: g, x, yinteger(int64) :: qinteger(int64) :: zs(0:1), xs(0:1), ys(0:1)integer(int32) :: old, nextzs(0) = a; zs(1) = bxs(0) = 1; xs(1) = 0ys(0) = 0; ys(1) = 1old = 1donext = ieor(old, 1)if (zs(old) == 0) exitq = 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 = nextend dox = xs(next)y = ys(next)g = a*x + b*yend subroutine extend_euclidpure type(modint) function div_m_m(mx, my) result(res)type(modint), intent(in) :: mx, myres = mx * inv(my)end function div_m_mpure type(modint) function div_i32_m(x, my) result(res)integer(int32), intent(in) :: xtype(modint), intent(in) :: myres = modint(x) / myend function div_i32_mpure type(modint) function div_i64_m(x, my) result(res)integer(int64), intent(in) :: xtype(modint), intent(in) :: myres = modint(x) / myend function div_i64_mpure type(modint) function div_m_i32(mx, y) result(res)type(modint), intent(in) :: mxinteger(int32), intent(in) :: yres = mx / modint(y)end function div_m_i32pure type(modint) function div_m_i64(mx, y) result(res)type(modint), intent(in) :: mxinteger(int64), intent(in) :: yres = mx / modint(y)end function div_m_i64pure type(modint) function pow_m_i32(mx, p) result(res)type(modint), intent(in) :: mxinteger(int32), intent(in) :: pres = mx ** int(p, int64)end function pow_m_i32pure type(modint) function pow_m_i64(mx, p) result(res)type(modint), intent(in) :: mxinteger(int64), intent(in) :: ptype(modint) :: mv, mx_poweredinteger(int64) :: powmv = 1mx_powered = mxpow = pdo while (pow /= 0)if (iand(pow, b'1') == 1) thenmv = mv * mx_poweredend ifmx_powered = mx_powered * mx_poweredpow = ishft(pow, -1)end dores = mvend function pow_m_i64pure type(modint) function combination_m_m(mn, mr) result(res)type(modint), intent(in) :: mn, mrinteger(int64) :: ires = modint(1)do i = 1, mr%to_i64()res = res * (mn%to_i64()-i+1) / iend doend function combination_m_mpure type(modint) function combination_m_i32(mn, r) result(res)type(modint), intent(in) :: mninteger(int32), intent(in) :: rres = combination(mn, modint(r))end function combination_m_i32pure type(modint) function combination_m_i64(mn, r) result(res)type(modint), intent(in) :: mninteger(int64), intent(in) :: rres = combination(mn, modint(r))end function combination_m_i64pure type(modint) function combination_i32_m(n, mr) result(res)integer(int32), intent(in) :: ntype(modint), intent(in) :: mrres = combination(modint(n), mr)end function combination_i32_mpure type(modint) function combination_i64_m(n, mr) result(res)integer(int64), intent(in) :: ntype(modint), intent(in) :: mrres = combination(modint(n), mr)end function combination_i64_mend module modint_mprogram yukicoder_2494use, intrinsic :: iso_fortran_envuse union_find_muse modint_mimplicit noneinteger(int32) :: n, m, u, vinteger(int64), allocatable :: arr(:)type(modint) :: anstype(modint), allocatable :: summ(:)type(union_find) :: ufinteger(int32) :: iread(input_unit, *) n, mallocate(arr(n))read(input_unit, *) arr(:)call uf%init(n)do i = 1, mread(input_unit, *) u, vcall uf%union(u, v)end doallocate(summ(n), source = modint(0))ans = modint(1)do i = 1, nsumm(uf%root(i)) = summ(uf%root(i)) + arr(i)end dodo i = 1, nans = ans * summ(uf%root(i))end dowrite(output_unit, '(i0)') ansend program yukicoder_2494