結果
問題 | No.1299 Random Array Score |
ユーザー | hakatashi |
提出日時 | 2020-11-27 21:54:23 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 5,710 bytes |
コンパイル時間 | 11,228 ms |
コンパイル使用メモリ | 295,332 KB |
実行使用メモリ | 21,820 KB |
最終ジャッジ日時 | 2024-06-30 21:43:38 |
合計ジャッジ時間 | 13,469 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
lib C;fun strtoll(s: UInt8*,p: UInt8**,b: Int32): Int64;endclass String;def to_i64;C.strtoll(self,nil,10);end;end# ac-library.cr by hakatashi https://github.com/google/ac-library.cr## Copyright 2020 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 AtCodermacro static_modint(name, modulo)module AtCoderrecord {{name}}, value : Int64 do@@factorials = Array(self).new(100_000_i64) # Change here to improve performanceMOD = {{modulo}}def self.factorial(n)if @@factorials.empty?@@factorials << self.new(1_i64)end@@factorials.size.upto(n) do |i|@@factorials << @@factorials.last * iend@@factorials[n]enddef self.permutation(n, k)raise ArgumentError.new("k cannot be greater than n") unless n >= kfactorial(n) // factorial(n - k)enddef self.combination(n, k)raise ArgumentError.new("k cannot be greater than n") unless n >= kpermutation(n, k) // @@factorials[k]enddef self.repeated_combination(n, k)combination(n + k - 1, k)enddef 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)enddef self.zeroself.new(0_i64)enddef invg, x = self.class.extended_gcd(@value, MOD)self.class.new(x % MOD)enddef +(value)self.class.new((@value + value.to_i64 % MOD) % MOD)enddef -(value)self.class.new((@value + MOD - value.to_i64 % MOD) % MOD)enddef *(value)self.class.new((@value * value.to_i64 % MOD) % MOD)enddef /(value : self)raise DivisionByZeroError.new if value == 0self * value.invenddef /(value)raise DivisionByZeroError.new if value == 0self * self.class.new(value.to_i64 % MOD).invenddef //(value)self./(value)enddef **(value)b = value > 0 ? self : self.inve = value.absret = self.class.new(1_i64)while e > 0if e % 2 == 1ret *= bendb *= be //= 2endretenddef <<(value)self * self.class.new(2_i64) ** valueenddef sqrtz = self.class.new(1_i64)until z ** ((MOD - 1) // 2) == MOD - 1z += 1endq = MOD - 1m = 0while q % 2 == 0q //= 2m += 1endc = z ** qt = self ** qr = self ** ((q + 1) // 2)m.downto(2) do |i|tmp = t ** (2 ** (i - 2))if tmp != 1r *= ct *= c ** 2endc *= cendif r * r == selfr.to_i64 * 2 <= MOD ? r : -relsenilendenddef to_i64@valueenddef ==(value : self)@value == value.to_i64enddef ==(value)@value == valueenddef -self.class.new(0_i64) - selfenddef +selfenddef absselfend# ac-library compatibilitydef pow(value)self.**(value)enddef valself.to_i64end# ModInt shouldn't be compareddef <(value)raise NotImplementedError.new("<")enddef <=(value)raise NotImplementedError.new("<=")enddef <(value)raise NotImplementedError.new("<")enddef >=(value)raise NotImplementedError.new(">=")enddelegate to_s, to: @valuedelegate inspect, to: @valueendendstruct Intdef +(value : AtCoder::{{name}})value + selfenddef -(value : AtCoder::{{name}})-value + selfenddef *(value : AtCoder::{{name}})value * selfenddef //(value : AtCoder::{{name}})value.inv * selfenddef /(value : AtCoder::{{name}})self // valueenddef ==(value : AtCoder::{{name}})value == selfendendendendAtCoder.static_modint(ModInt1000000007, 1_000_000_007_i64)AtCoder.static_modint(ModInt998244353, 998_244_353_i64)alias Mint = AtCoder::ModInt998244353n, k = read_line.split.map(&.to_i64)ais = read_line.split.map {|a| Mint.new(a.to_i64)}p Mint.new(2_i64) ** k * ais.sum