結果

問題 No.3004 ヤング図形
ユーザー PNJ
提出日時 2025-01-17 23:34:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,702 ms / 4,000 ms
コード長 8,584 bytes
コンパイル時間 858 ms
コンパイル使用メモリ 81,536 KB
実行使用メモリ 404,944 KB
最終ジャッジ日時 2025-01-17 23:36:33
合計ジャッジ時間 94,358 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

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):
  if n <= 10 ** 7:
    return 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