結果

問題 No.3004 ヤング図形
ユーザー PNJ
提出日時 2025-01-17 23:31:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 8,546 bytes
コンパイル時間 2,315 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 405,112 KB
最終ジャッジ日時 2025-01-17 23:33:48
合計ジャッジ時間 113,477 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 24 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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

mod = 998244353
n = 10 ** 7
inv = [1 for j in range(n + 1)]
for a in range(2, n + 1):
# ax + py = 1 <=> rx + p(-x - qy) = -q => x = -(inv[r]) * (p // a) (r = p % a)
res = (mod - inv[mod % a]) * (mod // a)
inv[a] = res % mod
fact = [1 for i in range(n + 1)]
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % mod
fact_inv = [1 for i in range(n + 1)]
fact_inv[-1] = pow(fact[-1], mod - 2, mod)
for i in range(n, 0, -1):
fact_inv[i - 1] = fact_inv[i] * i % mod
def binom(n, r):
if n < r or n < 0 or r < 0:
return 0
res = fact_inv[n - r] * fact_inv[r] % mod
res *= fact[n]
res %= mod
return res
def NTT_info(mod):
if mod == 998244353:
return (23, 31, 0)
if mod == 120586241:
return (20, 74066978, 1)
if mod == 167772161:
return (25, 17, 2)
if mod == 469762049:
return (26, 30, 3)
if mod == 754974721:
return (24, 362, 4)
if mod == 880803841:
return (23, 211, 5)
if mod == 924844033:
return (21, 44009197, 6)
if mod == 943718401:
return (22, 663003469, 7)
if mod == 1045430273:
return (20, 363, 8)
if mod == 1051721729:
return (20, 330, 9)
if mod == 1053818881:
return (20, 2789, 10)
return (0, -1, -1)
def prepared_fft(mod = 998244353):
rank2 = NTT_info(mod)[0]
root, iroot = [0] * 30, [0] * 30
rate2, irate2 = [0] * 30, [0] * 30
rate3, irate3 = [0] * 30, [0] * 30
root[rank2] = NTT_info(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 = [[] for _ in range(11)], [[] for _ in range(11)], [[] for _ in range(11)], [[] for _ in range(11)], [[]
    for _ in range(11)], [[] for _ in range(11)]
def ntt(a, inverse = 0, mod = 998244353):
idx = NTT_info(mod)[2]
if len(root[idx]) == 0:
root[idx], iroot[idx], rate2[idx], irate2[idx], rate3[idx], irate3[idx] = prepared_fft(mod)
n = len(a)
h = (n - 1).bit_length()
assert (n == 1 << h)
if inverse == 0:
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[idx][((~s & -~s) - 1).bit_length()] % mod
le += 1
else:
p = 1 << (h - le - 2)
rot, imag = 1, root[idx][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[idx][((~s & -~s) - 1).bit_length()] % mod
le += 2
else:
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[idx][((~s & -~s) - 1).bit_length()] % mod
le -= 1
else:
p = 1 << (h - le)
irot, iimag = 1, iroot[idx][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[idx][((~s & -~s) - 1).bit_length()]
irot %= mod
le -= 2
def convolution_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 convolution_ntt(a, b, mod = 998244353):
s = a[:]
t = b[:]
n = len(s)
m = len(t)
if min(n, m) <= 60:
return convolution_naive(s, t, mod)
le = 1
while le < n + m - 1:
le *= 2
s += [0] * (le - n)
t += [0] * (le - m)
ntt(s, 0, mod)
ntt(t, 0, mod)
for i in range(le):
s[i] = s[i] * t[i] % mod
ntt(s, 1, 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 Garner(Rem, MOD, mod):
Mod = MOD[:]
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]
def convolution_garner(f, g, mod):
MOD = [167772161, 469762049, 754974721]
flag = 0
if (mod - 1) * (mod - 1) * min(len(f), len(g)) >= 167772161 * 469762049 * 754974721:
MOD += [880803841, 998244353]
flag = 1
H = []
for i in range(len(MOD)):
H.append(convolution_ntt(f, g, MOD[i]))
h = []
for i in range(len(H[0])):
Rem = [H[0][i], H[1][i], H[2][i]]
if flag:
Rem += [H[3][i], H[4][i]]
h.append(Garner(Rem, MOD, mod) % mod)
return h
def convolution(f, g, mod = 998244353):
if NTT_info(mod)[1] == -1:
return convolution_garner(f, g, mod)
return convolution_ntt(f, g, mod)
# https://suisen-cp.github.io/cp-library-cpp/library/polynomial/shift_of_sampling_points.hpp
def shift_of_sampling_points(Y, M, c, mod = 998244353):
N = len(Y)
# step1
A = [Y[j] * fact_inv[j] % mod for j in range(N)]
B = [fact_inv[i] * pow(-1, i % 2) % mod for i in range(N)]
f = convolution(A, B, mod)[:N]
# step2
A = [f[i] * fact[i] % mod for i in range(N)]
A = A[::-1]
B = [fact_inv[j] for j in range(N)]
b = 1
for i in range(N):
B[i] = B[i] * b % mod
b = b * (c - i) % mod
B = convolution(A, B, mod)[:N]
A = [B[N - 1 - j] * fact_inv[j] % mod for j in range(N)]
B = [fact_inv[i] for i in range(M)]
res = convolution(A, B, mod)[:M]
for i in range(M):
res[i] = res[i] * fact[i] % mod
return res
K = 9
B = 1 << K
P = mod
i = 1
point = [1,3]
while i < K:
t = 1 << i
f = point + shift_of_sampling_points(point,3 * t,t)
point = [0 for j in range(2 * t)]
for j in range(2 * t):
point[j] = (f[2 * j] * f[2 * j + 1] % mod) * (t * (2 * j + 1) % mod) % mod
i += 1
point = shift_of_sampling_points(point,P // B,0)
T = [1] + point
for i in range(1,len(T)):
T[i] = T[i] * (i * B) % mod
for i in range(len(T) - 1):
T[i + 1] = T[i + 1] * T[i] % mod
def get_fact(n):
r = n % B
q = n // B
res = T[q]
for i in range(1, r + 1):
res = res * (q * B + i) % mod
return res
S = 0
ans = 1
for _ in range(int(input())):
L, M = map(int, input().split())
res = get_fact(L)
res = pow(res, -1, mod)
res = pow(res, M, mod)
ans = ans * res % mod
res = get_fact(M)
res = pow(res, -1, mod)
ans = ans * res % mod
S += L * M
ans = ans * get_fact(S) % mod
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0