結果
問題 | No.2326 Factorial to the Power of Factorial to the... |
ユーザー |
|
提出日時 | 2023-05-28 15:24:09 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 7,336 bytes |
コンパイル時間 | 17,036 ms |
コンパイル使用メモリ | 296,420 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-27 06:29:20 |
合計ジャッジ時間 | 18,622 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
def int(b = 0)read_line.to_i64 + benddef ints(b = 0)read_line.split.map { |x| x.to_i64 + b }enddef strread_line.chompendmacro chmax(a, b)({{a}} < {{b}} && ({{a}} = {{b}}))endmacro chmin(a, b)({{a}} > {{b}} && ({{a}} = {{b}}))endmacro make_array(s, x)Array.new({{ s[0] }}) {{% if s[1..s.size].empty? %}; {{ x }}{% else %}; make_array({{ s[1..s.size] }}, {{ x }}) {% end %}}endOO = (1_i64 << 62) - (1_i64 << 31)def modinv(a : Int64, mod : Int64) : Int64b = modu = 1_i64v = 0_i64until b == 0t = a // ba -= t * ba, b = b, au -= t * vu, v = v, uendu % modenddef modpow(a : Int64, n : Int64, mod : Int64) : Int64res = 1_i64until n == 0res = res * a % mod if n.odd?a = a * a % modn >>= 1endresendmacro static_modint(modint, mod)struct {{ modint }}include Comparable({{ modint }})MOD = {{ mod }}getter val : Int64delegate popcount, to: valdelegate trailing_zeros_count, to: valdef initialize@val = 0enddef initialize(@val : Int64)@val %= {{ mod }}enddef + : self; self enddef - : self; {{ modint }}.new -@val enddef +(other : self) : self; {{ modint }}.new @val + other.val enddef -(other : self) : self; {{ modint }}.new @val - other.val enddef *(other : self) : self; {{ modint }}.new @val * other.val enddef /(other : self) : self; {{ modint }}.new @val * other.inv.val enddef //(other : self) : self; self / other enddef +(other : Int) : self; {{ modint }}.new @val + other enddef -(other : Int) : self; {{ modint }}.new @val - other enddef *(other : Int) : self; {{ modint }}.new @val * other enddef **(other : Int) : self; self.pow(other.to_i64) enddef /(other : Int) : self; {{ modint }}.new @val * modinv(other.to_i64, {{ mod }}) enddef //(other : Int) : self; self / other enddef <=>(other : self) : Int32; @val <=> other.val enddef inv : self{{ modint }}.new modinv(@val, {{ mod }})enddef pow(n : Int64) : self{{ modint }}.new modpow(@val, n, {{ mod }})enddef abs : selfselfenddef zero? : Bool@val == 0_i64enddef self.zero : self{{ modint }}.new 0_i64enddef clone{{ modint }}.new @valenddef to_i; @val.to_i enddef to_i32; @val.to_i32 enddef to_i64; @val.to_i64 enddef to_s(io : IO); io << @val enddef inspect(io : IO); to_s(io) endendstruct Intdef to_m{{ modint }}.new self.to_i64enddef +(other : {{ modint }}) : {{ modint }}; {{ modint }}.new self.to_i64 % {{ mod }} + other.val enddef -(other : {{ modint }}) : {{ modint }}; {{ modint }}.new self.to_i64 % {{ mod }} - other.val enddef *(other : {{ modint }}) : {{ modint }}; {{ modint }}.new self.to_i64 % {{ mod }} * other.val enddef /(other : {{ modint }}) : {{ modint }}; {{ modint }}.new self.to_i64 % {{ mod }} * other.inv.val enddef //(other : {{ modint }}) : {{ modint }}; self.to_i64 / other endendendstatic_modint(ModInt, 1_000_000_007_i64)# static_modint(ModInt, 998_244_353_i64)# .O,# :o.# 'd' :c;. c# lc dKl ;d,.,cl:. oOx.# .x. .,. 'd:.......:ll;. 'lc# .;0; .ol............'col;.# .:do;xl cd'.................,col;.# .,cdd:' od 'x;........:..............':ol;.# ..;lddc,. od od....l:...;x.........,........,lo;# .,:loodl;. .,,kx. .kk:....k,...lo........od.........;.:x,# .,coool:,. ....;lkodl....O:...dk.......;Oo........:x...oo# :dl;'. .lk:...Ok...xkc......xcx.......,k'....:x# ;k, :x:.Olx'.O'd;....;o.O......;Oc......cx# O, . ;xO;.cOO..ll,..l: x,...,dck,.......dc# k: lKd oO. KK .;cld; dc;lOc.;d........,0# dl . cx.cO. .,.KW..x'.........0.# oc .ll;. :k.l: ;l,k,...;:.....0.# o, kkxkOOOOOOOOOkkkkxl:'. ;x.,. .dOoccod:.....cO# x..o. lOxxxxxxxxxxxxxxxxxxkXOOdc' oc .l;,,,;coo:...ol......o0,# O ' xOxxxxxxxxxxxxxxxxxxxxKOxxkOOd; .0. '0:ccc:,,,0ccd;....;lx0l# .x .Okxxxxxxxxxxxxxxxxxxxxx0KxxxxxxkOo. O' do'''''''OllOkoooolckl# ;l .OkxxxxxxxxxxxxxxxxxxxxxxOKxxxxxkOxk0l kkollll0kdoddxkK0Oxllooool.# c: kKxxxxxxxxxxxxxxxxxxxxxxx0XkxxxxkXxxxOO k' ;d. .k,....':ok0dc;.. .'::# o, xO00xxxxxxxxxxxxxxxxxxxxxxKOKxxxxxXdoOk0; .O ;d .k. .cd,ckccc;lx,# d, c0xx0Kkxxxxxxxxxxxxxxxxxxx0O.KkxxxkX. .0K; lk:lOo;;Oo;kd; ' .x;:c .# d, .0KxxxkK0kxxxxxxxxxxxxxxxx0k. l0xxxOx O0 'O::k; .kckO: Okollxxkx. k.# d, xod0xxxxK00OxxxxxxxxxxxxO0l. 'XxxkK' ;K, .Oxxo. .o x: ;O;;xo..K. l:# l; 0:;d0xxxkO.;ok0OkO00OkO0l. KkkKc';d0, ;olxx ,dd; 'Kkkk, 'Oc 'x# :l K:;;o0kxxKc .':c..:o,. O0OlO0Kd. 'ol. :d lO' ;00x;. ck' O.# 'x 0c;;;cO0xkXk, '. cdk00x..cOx ol .od. ,c. 'k; d;# 0. kl;;;;;oO0OK0, ,ccO00KOokk.'x. o: 'cx0; .::c:. od ;d# ;d..xd:;;;;;cdkkk,... ..';llc::,... ;d..xkc .klld. ol ol .k# ,llokkolcccloddkK0K00ck00xodoo:. cl ' .o..d: c. ,k k.# .,:c::;,.. ;d .0;k. ;lodxkKo .d' :x;'.....:xc lc# lx :OOOol 'O :o. dOooodd0. .O# lxc:,k:O .d; ll .dc ld;;;;O' l;# .c, dk:k;.k oOcc,,O. ,x. Oc;;;x: x.# .ld.'lkd;,:cdlc;;0, .:' dxcc:;,'kdllld0;',.. ;loodoool# ,ol. .oo. ...' .:::cccl:. :x. .............';codOc;;;;;;;;# :kd, co .'c, 'k. ,dx:;;;;;;# .:llld;,;:....O' .x: .ko;;;;;;# 'lkcodxdxO. ;x, :kc;;;;;;# ;k;;;;;;dx o0' ;Kd;;;;;MOD = 10_i64**9 + 7n, p = ints# n! を mod p で求めるfact = ModInt.new(1)(1..n).each do |i|fact *= iend# n! を p - 1 で割ったあまりrem = 1_i64(1..n).each do |i|rem *= i % (MOD - 1)rem %= MOD - 1endt = fact ** remsum = 0_i64i = 1_i64while n // (p ** i) > 0sum += n // (p ** i)i += 1endputs sum * t