結果
| 問題 | No.2917 二重木 |
| ユーザー |
 PNJ
|
| 提出日時 | 2024-10-05 00:04:15 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,157 bytes |
| コンパイル時間 | 134 ms |
| コンパイル使用メモリ | 81,812 KB |
| 実行使用メモリ | 86,988 KB |
| 最終ジャッジ日時 | 2024-10-05 00:04:51 |
| 合計ジャッジ時間 | 33,317 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 40 ms
54,336 KB |
| testcase_01 | AC | 39 ms
54,340 KB |
| testcase_02 | AC | 38 ms
55,628 KB |
| testcase_03 | AC | 37 ms
54,176 KB |
| testcase_04 | AC | 38 ms
54,784 KB |
| testcase_05 | AC | 36 ms
54,992 KB |
| testcase_06 | AC | 40 ms
55,860 KB |
| testcase_07 | AC | 39 ms
54,908 KB |
| testcase_08 | AC | 42 ms
62,152 KB |
| testcase_09 | AC | 43 ms
61,588 KB |
| testcase_10 | AC | 43 ms
60,956 KB |
| testcase_11 | AC | 44 ms
61,220 KB |
| testcase_12 | AC | 42 ms
61,992 KB |
| testcase_13 | AC | 42 ms
62,020 KB |
| testcase_14 | AC | 44 ms
61,444 KB |
| testcase_15 | AC | 38 ms
54,280 KB |
| testcase_16 | AC | 36 ms
55,364 KB |
| testcase_17 | AC | 35 ms
55,000 KB |
| testcase_18 | AC | 40 ms
54,464 KB |
| testcase_19 | AC | 40 ms
54,948 KB |
| testcase_20 | AC | 150 ms
77,148 KB |
| testcase_21 | AC | 357 ms
78,688 KB |
| testcase_22 | AC | 792 ms
79,888 KB |
| testcase_23 | AC | 36 ms
53,792 KB |
| testcase_24 | AC | 1,346 ms
80,940 KB |
| testcase_25 | AC | 1,613 ms
81,760 KB |
| testcase_26 | AC | 2,106 ms
83,424 KB |
| testcase_27 | AC | 39 ms
54,888 KB |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
| testcase_30 | TLE | - |
| testcase_31 | TLE | - |
| testcase_32 | TLE | - |
| testcase_33 | TLE | - |
| testcase_34 | TLE | - |
ソースコード
N,P = map(int,input().split())
if N == P:
print((N % 2) ^ 1)
exit()
mod,Mod,MOD = 1045430273,1051721729,1053818881
n = N
fact = [1 for i in range(n + 1)]
for i in range(1,n + 1):
fact[i] = fact[i - 1] * i % P
fact_inv = [1 for i in range(n + 1)]
fact_inv[-1] = pow(fact[-1],P - 2,P)
for i in range(n,0,-1):
fact_inv[i - 1] = fact_inv[i] * i % P
def binom(n,r):
res = fact[n] * (fact_inv[n - r] * fact_inv[r] % P) % P
return res
NTT_friend = [120586241,167772161,469762049,754974721,880803841,924844033,943718401,998244353,1045430273,1051721729,1053818881]
NTT_dict = {}
for i in range(len(NTT_friend)):
NTT_dict[NTT_friend[i]] = i
NTT_info = [[20,74066978],[25,17],[26,30],[24,362],[23,211],[21,44009197],[22,663003469],[23,31],[20,363],[20,330],[20,2789]]
def popcount(n):
c=(n&0x5555555555555555)+((n>>1)&0x5555555555555555)
c=(c&0x3333333333333333)+((c>>2)&0x3333333333333333)
c=(c&0x0f0f0f0f0f0f0f0f)+((c>>4)&0x0f0f0f0f0f0f0f0f)
c=(c&0x00ff00ff00ff00ff)+((c>>8)&0x00ff00ff00ff00ff)
c=(c&0x0000ffff0000ffff)+((c>>16)&0x0000ffff0000ffff)
c=(c&0x00000000ffffffff)+((c>>32)&0x00000000ffffffff)
return c
def topbit(n):
h = n.bit_length()
h -= 1
return h
def prepared_fft(mod = 998244353):
rank2 = NTT_info[NTT_dict[mod]][0]
root,iroot = [0] * 30,[0] * 30
rate2,irate2= [0] * 30,[0] * 30
rate3,irate3= [0] * 30,[0] * 30
root[rank2] = NTT_info[NTT_dict[mod]][1]
iroot[rank2] = pow(root[rank2],mod - 2,mod)
for i in range(rank2-1,-1,-1):
root[i] = root[i+1] * root[i+1] % mod
iroot[i] = iroot[i+1] * iroot[i+1] % mod
prod,iprod = 1,1
for i in range(rank2-1):
rate2[i] = root[i + 2] * prod % mod
irate2[i] = iroot[i + 2] * iprod % mod
prod = prod * iroot[i + 2] % mod
iprod = iprod * root[i + 2] % mod
prod,iprod = 1,1
for i in range(rank2-2):
rate3[i] = root[i + 3] * prod % mod
irate3[i] = iroot[i + 3] * iprod % mod
prod = prod * iroot[i + 3] % mod
iprod = iprod * root[i + 3] % mod
return root,iroot,rate2,irate2,rate3,irate3
root,iroot,rate2,irate2,rate3,irate3 = prepared_fft()
def ntt(a,mod = 998244353):
root,iroot,rate2,irate2,rate3,irate3 = prepared_fft(mod)
n = len(a)
h = topbit(n)
assert (n == 1 << h)
le = 0
while le < h:
if h - le == 1:
p = 1 << (h - le - 1)
rot = 1
for s in range(1 << le):
offset = s << (h - le)
for i in range(p):
l = a[i + offset]
r = a[i + offset + p] * rot % mod
a[i + offset] = (l + r) % mod
a[i + offset + p] = (l - r) % mod
rot = rot * rate2[topbit(~s & -~s)] % mod
le += 1
else:
p = 1 << (h - le - 2)
rot,imag = 1,root[2]
for s in range(1 << le):
rot2 = rot * rot % mod
rot3 = rot2 * rot % mod
offset = s << (h - le)
for i in range(p):
a0 = a[i + offset]
a1 = a[i + offset + p] * rot
a2 = a[i + offset + p * 2] * rot2
a3 = a[i + offset + p * 3] * rot3
a1na3imag = (a1 - a3) % mod * imag
a[i + offset] = (a0 + a2 + a1 + a3) % mod
a[i + offset + p] = (a0 + a2 - a1 - a3) % mod
a[i + offset + p * 2] = (a0 - a2 + a1na3imag) % mod
a[i + offset + p * 3] = (a0 - a2 - a1na3imag) % mod
rot = rot * rate3[topbit(~s & -~s)] % mod
le += 2
def intt(a,mod = 998244353):
root,iroot,rate2,irate2,rate3,irate3 = prepared_fft(mod)
n = len(a)
h = topbit(n)
assert (n == 1 << h)
coef = pow(n,mod - 2,mod)
for i in range(n):
a[i] = a[i] * coef % mod
le = h
while le:
if le == 1:
p = 1 << (h - le)
irot = 1
for s in range(1 << (le - 1)):
offset = s << (h - le + 1)
for i in range(p):
l = a[i + offset]
r = a[i + offset + p]
a[i + offset] = (l + r) % mod
a[i + offset + p] = (l - r) * irot % mod
irot = irot * irate2[topbit(~s & -~s)] % mod
le -= 1
else:
p = 1 << (h - le)
irot,iimag = 1,iroot[2]
for s in range(1 << (le - 2)):
irot2 = irot * irot % mod
irot3 = irot2 * irot % mod
offset = s << (h - le + 2)
for i in range(p):
a0 = a[i + offset]
a1 = a[i + offset + p]
a2 = a[i + offset + p * 2]
a3 = a[i + offset + p * 3]
a2na3iimag = (a2 - a3) * iimag % mod
a[i + offset] = (a0 + a1 + a2 + a3) % mod
a[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % mod
a[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2 % mod
a[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3 % mod
irot *= irate3[topbit(~s & -~s)]
irot %= mod
le -= 2
def convolute_naive(a,b,mod = 998244353):
res = [0] * (len(a) + len(b) - 1)
for i in range(len(a)):
for j in range(len(b)):
res[i+j] = (res[i+j] + a[i] * b[j] % mod) % mod
return res
def convolute(a,b,mod = 998244353):
s = a[:]
t = b[:]
n = len(s)
m = len(t)
if min(n,m) <= 60:
return convolute_naive(s,t,mod)
le = 1
while le < n + m - 1:
le *= 2
s += [0] * (le - n)
t += [0] * (le - m)
ntt(s,mod)
ntt(t,mod)
for i in range(le):
s[i] = s[i] * t[i] % mod
intt(s,mod)
s = s[:n + m - 1]
return s
def mod_inv(a,mod):
if mod == 1:
return 0
a %= mod
b,s,t = mod,1,0
while True:
if a == 1:
return s
t -= (b // a) * s
b %= a
if b == 1:
return t + mod
s -= (a // b) * t
a %= b
def gcd_inv(a,mod):
a %= mod
b,s,t = mod,1,0
while True:
if a == 0:
return (b,t + mod)
t -= (b // a) * s
b %= a
if b == 0:
return (a,s)
s -= (a // b) * t
a %= b
# (0,0)のとき存在しない.
def garner(Rem,Mod):
assert (len(Rem) == len(Mod))
r,m = 0,1
for i in range(len(Rem)):
assert (Mod[i])
Rem[i] %= Mod[i]
m1,r1 = Mod[i],Rem[i]
if m < m1:
m,m1,r,r1 = m1,m,r1,r
if m % m1 == 0:
if r % m1 != r1:
return (0,0)
g,im = gcd_inv(m,m1)
y = abs(r1 - r)
if y % g:
return (0,0)
u1 = m1 // g
y = y // g % u1
if (r > r1 and y != 0):
y = u1 - y
x = y * im % u1
r += x * m
m *= u1
return r
# Modの中身が互いに素じゃないとダメ
def Garner(Rem,Mod,mod):
assert (len(Rem) == len(Mod))
for i in range(len(Mod)):
if Mod[i] == mod:
return Rem[i]
Rem.append(0)
Mod.append(mod)
n = len(Mod)
coffs = [1] * n
constants = [0] * n
for i in range(n - 1):
v = (Rem[i] - constants[i]) * mod_inv(coffs[i],Mod[i]) % Mod[i]
for j in range(i + 1,n):
constants[j] = (constants[j] + coffs[j] * v) % Mod[j]
coffs[j] = (coffs[j] * Mod[i]) % Mod[j]
return constants[-1]
f = [1]
for i in range(1,N + 1):
c = pow(i + 1,i - 1,P) * fact_inv[i] % P
f.append(c)
ans = 0
g = [0] * N
g[0] = 1
for n in range(1,N + 1):
res = fact_inv[n] * pow(n,n - 2,P) % P
h = convolute(f,g,mod)
hh = convolute(f,g,Mod)
hhh = convolute(f,g,MOD)
for i in range(N + 1 - n):
g[i] = Garner([h[i],hh[i],hhh[i]],[mod,Mod,MOD],P) % P
res = res * g.pop() % P
ans += res
ans %= P
print(ans * fact[N] % P)