結果

問題 No.1670 Many Gacha
ユーザー lam6er
提出日時 2025-03-26 15:59:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 297 ms / 2,000 ms
コード長 1,227 bytes
コンパイル時間 646 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 118,116 KB
最終ジャッジ日時 2025-03-26 16:00:32
合計ジャッジ時間 9,095 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    # Precompute inverse and harmonic numbers
    maxH = N
    inv = [0] * (maxH + 2)
    inv[1] = 1
    for i in range(2, maxH + 1):
        inv[i] = pow(i, MOD - 2, MOD)
    
    H = [0] * (maxH + 2)
    for i in range(1, maxH + 1):
        H[i] = (H[i - 1] + inv[i]) % MOD
    
    # Compute B array
    B = []
    prev = 0
    for a in A:
        B.append(a - prev)
        prev = a
    
    # Compute s_i
    s = [0] * (M + 2)  # s[1..M]
    for i in range(M, 0, -1):
        s[i] = B[i-1] + s[i+1]
        if s[i] > N:
            raise ValueError("s_i exceeds N")
    
    ans = 0
    for i in range(M):
        current_B = B[i]
        current_A = A[i]
        s_i = s[i+1]  # s[i+1] corresponds to the i-th (0-based) in B
        s_i_minus_Bi = s_i - current_B
        
        h_si = H[s_i]
        if s_i_minus_Bi >= 0:
            h_part = (h_si - H[s_i_minus_Bi]) % MOD
        else:
            h_part = h_si % MOD
        
        term = current_A * h_part % MOD
        ans = (ans + term) % MOD
    
    print(ans % MOD)

if __name__ == '__main__':
    main()
0