結果

問題 No.2326 Factorial to the Power of Factorial to the...
ユーザー ngng628
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

def int(b = 0)
read_line.to_i64 + b
end
def ints(b = 0)
read_line.split.map { |x| x.to_i64 + b }
end
def str
read_line.chomp
end
macro chmax(a, b)
({{a}} < {{b}} && ({{a}} = {{b}}))
end
macro chmin(a, b)
({{a}} > {{b}} && ({{a}} = {{b}}))
end
macro make_array(s, x)
Array.new({{ s[0] }}) {
{% if s[1..s.size].empty? %}; {{ x }}
{% else %}; make_array({{ s[1..s.size] }}, {{ x }}) {% end %}
}
end
OO = (1_i64 << 62) - (1_i64 << 31)
def modinv(a : Int64, mod : Int64) : Int64
b = mod
u = 1_i64
v = 0_i64
until b == 0
t = a // b
a -= t * b
a, b = b, a
u -= t * v
u, v = v, u
end
u % mod
end
def modpow(a : Int64, n : Int64, mod : Int64) : Int64
res = 1_i64
until n == 0
res = res * a % mod if n.odd?
a = a * a % mod
n >>= 1
end
res
end
macro static_modint(modint, mod)
struct {{ modint }}
include Comparable({{ modint }})
MOD = {{ mod }}
getter val : Int64
delegate popcount, to: val
delegate trailing_zeros_count, to: val
def initialize
@val = 0
end
def initialize(@val : Int64)
@val %= {{ mod }}
end
def + : self; self end
def - : self; {{ modint }}.new -@val end
def +(other : self) : self; {{ modint }}.new @val + other.val end
def -(other : self) : self; {{ modint }}.new @val - other.val end
def *(other : self) : self; {{ modint }}.new @val * other.val end
def /(other : self) : self; {{ modint }}.new @val * other.inv.val end
def //(other : self) : self; self / other end
def +(other : Int) : self; {{ modint }}.new @val + other end
def -(other : Int) : self; {{ modint }}.new @val - other end
def *(other : Int) : self; {{ modint }}.new @val * other end
def **(other : Int) : self; self.pow(other.to_i64) end
def /(other : Int) : self; {{ modint }}.new @val * modinv(other.to_i64, {{ mod }}) end
def //(other : Int) : self; self / other end
def <=>(other : self) : Int32; @val <=> other.val end
def inv : self
{{ modint }}.new modinv(@val, {{ mod }})
end
def pow(n : Int64) : self
{{ modint }}.new modpow(@val, n, {{ mod }})
end
def abs : self
self
end
def zero? : Bool
@val == 0_i64
end
def self.zero : self
{{ modint }}.new 0_i64
end
def clone
{{ modint }}.new @val
end
def to_i; @val.to_i end
def to_i32; @val.to_i32 end
def to_i64; @val.to_i64 end
def to_s(io : IO); io << @val end
def inspect(io : IO); to_s(io) end
end
struct Int
def to_m
{{ modint }}.new self.to_i64
end
def +(other : {{ modint }}) : {{ modint }}; {{ modint }}.new self.to_i64 % {{ mod }} + other.val end
def -(other : {{ modint }}) : {{ modint }}; {{ modint }}.new self.to_i64 % {{ mod }} - other.val end
def *(other : {{ modint }}) : {{ modint }}; {{ modint }}.new self.to_i64 % {{ mod }} * other.val end
def /(other : {{ modint }}) : {{ modint }}; {{ modint }}.new self.to_i64 % {{ mod }} * other.inv.val end
def //(other : {{ modint }}) : {{ modint }}; self.to_i64 / other end
end
end
static_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 + 7
n, p = ints
# n! mod p
fact = ModInt.new(1)
(1..n).each do |i|
fact *= i
end
# n! p - 1
rem = 1_i64
(1..n).each do |i|
rem *= i % (MOD - 1)
rem %= MOD - 1
end
t = fact ** rem
sum = 0_i64
i = 1_i64
while n // (p ** i) > 0
sum += n // (p ** i)
i += 1
end
puts sum * t
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0