結果

問題 No.2600 Avator Height
コンテスト
ユーザー osada-yum
提出日時 2024-01-12 22:06:09
言語 Fortran
(gFortran 14.2.0)
結果
AC  
実行時間 158 ms / 2,000 ms
コード長 9,717 bytes
コンパイル時間 630 ms
コンパイル使用メモリ 36,608 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-27 22:22:48
合計ジャッジ時間 6,828 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

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_2600
  use, intrinsic :: iso_fortran_env
  use modint_m
  implicit none
  integer(int32), parameter :: maxi_val = 2 * 10**5
  integer(int32) :: q, n
  type(modint), allocatable :: rs(:), es(:)
  integer(int32) :: i
  read(input_unit, *) q
  allocate(rs(maxi_val), es(maxi_val))
  rs(1) = modint(1); rs(2) = modint(1)
  es(1) = modint(1); es(2) = modint(3)
  do i = 3, maxi_val
     rs(i) = rs(i - 2) + rs(i - 1)
     es(i) = es(i - 2) + es(i - 1)
  end do
  do i = 1, q
     read(input_unit, *) n
     write(output_unit, '(i0)') 5 * rs(n) ** 2 - es(n) ** 2
  end do
end program yukicoder_2600
0