結果
問題 | No.1578 A × B × C |
ユーザー | yuruhiya |
提出日時 | 2021-07-02 21:22:51 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 7,761 bytes |
コンパイル時間 | 13,498 ms |
コンパイル使用メモリ | 295,700 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-29 05:12:19 |
合計ジャッジ時間 | 14,343 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 1 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 1 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,944 KB |
testcase_15 | AC | 1 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 1 ms
6,944 KB |
testcase_18 | AC | 1 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 1 ms
6,940 KB |
testcase_21 | AC | 2 ms
6,940 KB |
testcase_22 | AC | 1 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 1 ms
6,944 KB |
ソースコード
# require "/math/Mint"# require "../atcoder/src/Math"# ac-library.cr by hakatashi https://github.com/google/ac-library.cr## Copyright 2021 Google LLC## Licensed under the Apache License, Version 2.0 (the "License");# you may not use this file except in compliance with the License.# You may obtain a copy of the License at## https://www.apache.org/licenses/LICENSE-2.0## Unless required by applicable law or agreed to in writing, software# distributed under the License is distributed on an "AS IS" BASIS,# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.# See the License for the specific language governing permissions and# limitations under the License.module AtCoder# Implements [ACL's Math library](https://atcoder.github.io/ac-library/master/document_en/math.html)module Mathdef self.extended_gcd(a, b)last_remainder, remainder = a.abs, b.absx, last_x, y, last_y = 0_i64, 1_i64, 1_i64, 0_i64while remainder != 0new_last_remainder = remainderquotient, remainder = last_remainder.divmod(remainder)last_remainder = new_last_remainderx, last_x = last_x - quotient * x, xy, last_y = last_y - quotient * y, yendreturn last_remainder, last_x * (a < 0 ? -1 : 1)end# Implements atcoder::inv_mod(value, modulo).def self.inv_mod(value, modulo)gcd, inv = extended_gcd(value, modulo)if gcd != 1raise ArgumentError.new("#{value} and #{modulo} are not coprime")endinv % moduloend# Simplified AtCoder::Math.pow_mod with support of Int64def self.pow_mod(base, exponent, modulo)if exponent == 0return base.class.zero + 1endif base == 0return baseendb = exponent > 0 ? base : inv_mod(base, modulo)e = exponent.absret = 1_i64while e > 0if e % 2 == 1ret = mul_mod(ret, b, modulo)endb = mul_mod(b, b, modulo)e //= 2endretend# Caluculates a * b % mod without overflow detection@[AlwaysInline]def self.mul_mod(a : Int64, b : Int64, mod : Int64)if mod < Int32::MAXreturn a * b % modend# 31-bit widtha_high = (a >> 32).to_u64# 32-bit widtha_low = (a & 0xFFFFFFFF).to_u64# 31-bit widthb_high = (b >> 32).to_u64# 32-bit widthb_low = (b & 0xFFFFFFFF).to_u64# 31-bit + 32-bit + 1-bit = 64-bitc = a_high * b_low + b_high * a_lowc_high = c >> 32c_low = c & 0xFFFFFFFF# 31-bit + 31-bitres_high = a_high * b_high + c_high# 32-bit + 32-bitres_low = a_low * b_lowres_low_high = res_low >> 32res_low_low = res_low & 0xFFFFFFFF# Overflowif res_low_high + c_low >= 0x100000000res_high += 1endres_low = (((res_low_high + c_low) & 0xFFFFFFFF) << 32) | res_low_low(((res_high.to_i128 << 64) | res_low) % mod).to_i64end@[AlwaysInline]def self.mul_mod(a, b, mod)typeof(mod).new(a.to_i64 * b % mod)end# Implements atcoder::crt(remainders, modulos).def self.crt(remainders, modulos)raise ArgumentError.new unless remainders.size == modulos.sizetotal_modulo = 1_i64answer = 0_i64remainders.zip(modulos).each do |(remainder, modulo)|gcd, p = extended_gcd(total_modulo, modulo)if (remainder - answer) % gcd != 0return 0_i64, 0_i64endtmp = (remainder - answer) // gcd * p % (modulo // gcd)answer += total_modulo * tmptotal_modulo *= modulo // gcdendreturn answer % total_modulo, total_moduloend# Implements atcoder::floor_sum(n, m, a, b).def self.floor_sum(n, m, a, b)n, m, a, b = n.to_i64, m.to_i64, a.to_i64, b.to_i64res = 0_i64if a < 0a2 = a % mres -= n * (n - 1) // 2 * ((a2 - a) // m)a = a2endif b < 0b2 = b % mres -= n * ((b2 - b) // m)b = b2endres + floor_sum_unsigned(n, m, a, b)endprivate def self.floor_sum_unsigned(n, m, a, b)res = 0_i64loop doif a >= mres += n * (n - 1) // 2 * (a // m)a = a % mendif b >= mres += n * (b // m)b = b % mendy_max = a * n + bbreak if y_max < mn = y_max // mb = y_max % mm, a = a, mendresendendendmacro static_modint(name, mod)struct {{name}}MOD = {{mod}}i64def self.zeronewenddef self.raw(value : Int64)result = newresult.value = valueresultendgetter value : Int64def initialize@value = 0i64enddef initialize(value)@value = value.to_i64 % MODenddef initialize(m : self)@value = m.valueendprotected def value=(value : Int64)@value = valueenddef ==(m : self)value == m.valueenddef ==(m)value == menddef + : selfselfenddef - : selfself.class.raw(value != 0 ? MOD &- value : 0i64)enddef +(v)self + self.class.new(v)enddef +(m : self)x = value &+ m.valuex &-= MOD if x >= MODself.class.raw(x)enddef -(v)self - self.class.new(v)enddef -(m : self)x = value &- m.valuex &+= MOD if x < 0self.class.raw(x)enddef *(v)self * self.class.new(v)enddef *(m : self)self.class.new(value &* m.value)enddef /(v)self / self.class.new(v)enddef /(m : self)raise DivisionByZeroError.new if m.value == 0a, b, u, v = m.value, MOD, 1i64, 0i64while b != 0t = a // ba &-= t &* ba, b = b, au &-= t &* vu, v = v, uendself.class.new(value &* u)enddef //(v)self / venddef **(exponent : Int)t, res = self, self.class.raw(1i64)while exponent > 0res *= t if exponent & 1 == 1t *= texponent >>= 1endresend{% for op in %w[< <= > >=] %}def {{op.id}}(other)raise NotImplementedError.new({{op}})end{% end %}def invself.class.raw AtCoder::Math.inv_mod(value, MOD)enddef succself.class.raw(value != MOD &- 1 ? value &+ 1 : 0i64)enddef predself.class.raw(value != 0 ? value &- 1 : MOD &- 1)enddef absselfenddef to_i64 : Int64valueenddelegate to_s, to: @valuedelegate inspect, to: @valueend{% to = ("to_" + name.stringify.downcase.gsub(/mint|modint/, "m")).id %}struct Int{% for op in %w[+ - * / //] %}def {{op.id}}(value : {{name}}){{to}} {{op.id}} valueend{% end %}{% for op in %w[< <= > >=] %}def {{op.id}}(m : {{name}})raise NotImplementedError.new({{op}})end{% end %}def {{to}} : {{name}}{{name}}.new(self)endendclass Stringdef {{to}} : {{name}}{{name}}.new(self)endendendstatic_modint(Mint, 1000000007)static_modint(Mint2, 998244353)# require "/math/powmod"struct Intdef powmod(exp : T, mod : self) forall Tn = self % modres = typeof(self).new(1)while exp > 0res = res * n % mod if exp.odd?n = n * n % modexp >>= 1endresendenda, b, c = read_line.split.map(&.to_m)k = read_line.to_i64puts (a*b*c)**(2i64.powmod(k, Mint::MOD - 1))