結果

問題 No.3089 Base M Numbers, But Only 0~9
コンテスト
ユーザー nasutarou1341
提出日時 2025-04-04 23:22:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 293 ms / 2,000 ms
コード長 1,807 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 103,708 KB
最終ジャッジ日時 2025-04-04 23:22:11
合計ジャッジ時間 5,966 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invpowL(s, a, n): # a^-x (0 <= x <= n)リスト
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L
  def invL(s, n): # 0 <= x <= n 逆元リスト
    I = [0, 1]
    for i in range(2, n + 1):
      I.append(s.MOD - I[s.MOD % i] * (s.MOD // i) % s.MOD)
    return I

def yu(a, e, c):
  return ((a + e) * c // 2) % MOD

M = int(input())
N = input()
MOD = 998244353

def nasu(M, N):

  D = [0] * 10
  C = [0] * 10
  for i in range(10):
    C[i] = M // 10
    if i < M % 10: C[i] += 1
    D[i] = yu(i, i + 10 * (C[i] - 1), C[i])

  p = 0
  for p in range(len(N)):
    if N[p] != "0": break
  else:
    p = len(N)
  if p != 0: p = 1

  t = 1
  L = []
  CL = []
  i = len(N) - 1
  for a in N[::-1]:
    n = int(a)
    L.append(t * D[n] % MOD)
    CL.append(C[n])
    if i < p: CL[-1] -= 1
    t *= M
    t %= MOD
    i -= 1

  if min(CL) < 0: 1 / 0

  k = 1
  for c in CL:
    k *= c
    k %= MOD

  inv = Inv(MOD)
  ans = 0
  for i in range(len(L)):
    x = L[i]
    c = k * inv.invx(CL[i]) % MOD
    ans += x * c % MOD
    ans %= MOD

  return ans % MOD

def gutyoku(M, N):
  ans = 0
  for i in range(M ** len(N)):
    a = i
    for n in N[::-1]:
      if (a % M) % 10 != int(n): break
      if a == 0: break
      a //= M
    else:
      ans += i
  return ans

ans = nasu(M, N)
print(ans)
  
# for i in range(10, 100):
#   print(i)
#   for j in range(1000):
#     n = "0" + str(j)
#     a = nasu(i, n)
#     g = gutyoku(i, n)
#     if a != g:
#       print(i, n, a, g)
#       break
0