結果

問題 No.3089 Base M Numbers, But Only 0~9
ユーザー nasutarou1341
提出日時 2025-04-04 22:45:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,246 bytes
コンパイル時間 1,004 ms
コンパイル使用メモリ 82,144 KB
実行使用メモリ 103,584 KB
最終ジャッジ日時 2025-04-04 22:45:41
合計ジャッジ時間 5,152 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 18 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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

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)

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

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

print(ans % MOD)
0