結果

問題 No.2905 Nabeatsu Integration
コンテスト
ユーザー vwxyz
提出日時 2024-09-27 22:33:32
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 966 bytes
コンパイル時間 295 ms
コンパイル使用メモリ 81,848 KB
実行使用メモリ 146,748 KB
最終ジャッジ日時 2024-09-27 22:33:58
合計ジャッジ時間 14,352 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 1
other WA * 26 RE * 30 MLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def Z_algorithm(lst):
    le=len(lst)
    LCP=[None]*le
    LCP[0]=le
    L,R=0,0
    for i in range(1,le):
        if i<R:
            x=LCP[i-L]
            if x<R-i:
                LCP[i]=x
            elif R-i<x:
                LCP[i]=R-i
            else:
                while R<le and lst[R-i]==lst[R]:
                    R+=1
                LCP[i]=R-i
                L=i
        else:
            R=max(R,i)
            while R<le and lst[R-i]==lst[R]:
                R+=1
            LCP[i]=R-i
            L=i
    return LCP

S=input()
lcp=Z_algorithm(S)
lcp[0]=0
mod=998244353
N=len(S)
A=[None]*(N+1)
B=[None]*(N+1)
A[0]=1
B[0]=0
inve10=pow(10,mod-2,mod)
for i in range(N):
    if S[i]==S[0]:
        A[i+1]=(10*A[i]-9*A[lcp[i]])%mod
        B[i+1]=(10*B[i]-9*B[lcp[i]]-10)%mod
    else:
        A[i+1]=(10*A[i]-8*A[lcp[i]]-A[1])%mod
        B[i+1]=(10*B[i]-8*B[lcp[i]]-B[1]-10)%mod
ans=(-B[N])*pow(A[N],mod-2,mod)%mod
ans-=(N-1)
ans%=mod
print(ans)
0