結果

問題 No.3089 Base M Numbers, But Only 0~9
コンテスト
ユーザー titia
提出日時 2025-05-08 02:09:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 162 ms / 2,000 ms
コード長 630 bytes
コンパイル時間 453 ms
コンパイル使用メモリ 81,676 KB
実行使用メモリ 79,364 KB
最終ジャッジ日時 2025-05-08 02:10:02
合計ジャッジ時間 3,293 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

mod=998244353

M=int(input())
N=input().strip()

score=0
now=1
for i in range(len(N)-1,-1,-1):
    score=score+int(N[i])*now
    now=now*M%mod

LEN=len(N)
ANS=0

ko=1
SUM=0
now=1

DP=[0]*LEN
KO=[0]*LEN

for i in range(LEN-1,-1,-1):
    x=int(N[i])
    ko2=(M-x+9)//10

    # 初項x*now、交差now*10、項数ko2

    S=(x*now + x*now + (now*10) * (ko2-1))*ko2//2%mod
    #print(x*now,now*10,ko2,S)

    SUM=SUM*ko2+S*ko
    ko=ko*ko2

    now=now*M%mod

    SUM%=mod
    ko%=mod

    #print(SUM,ko)

    DP[i]=SUM
    KO[i]=ko

if N[0]=="0":
    print((SUM-DP[1])%mod)
else:
    print(SUM)
0