結果

問題 No.2833 Count Taiko Results
コンテスト
ユーザー LyricalMaestro
提出日時 2025-05-16 02:36:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 522 ms / 2,000 ms
コード長 1,394 bytes
コンパイル時間 432 ms
コンパイル使用メモリ 82,700 KB
実行使用メモリ 144,232 KB
最終ジャッジ日時 2025-05-16 02:36:45
合計ジャッジ時間 14,906 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2833

MOD = 998244353

def solve(N, K, A, B):
    cum_prod_list = [0] * (N + 1)
    cum_prod = 1
    cum_prod_list[0] = cum_prod
    cum_inv_prod_list = [0] * (N + 1)
    cum_inv_prod = 1
    cum_inv_prod_list[0 ]= cum_inv_prod
    for i in range(N):
        a = A[i]
        cum_prod *= a
        cum_prod %= MOD
        cum_prod_list[i + 1] = cum_prod

        inv_a = pow(a, MOD - 2, MOD)
        cum_inv_prod *= inv_a
        cum_inv_prod %= MOD
        cum_inv_prod_list[i + 1] = cum_inv_prod

    dp = [0] * (N + 2)
    cum_dp = [0] * (N + 2)
    dp[0] = 1
    cum_dp[0] = 1
    for i in range(N + 1):
        if i < N:
            b = B[i]
        else:
            b = 1

        if i - (K + 1) >= 0:
            x = (cum_dp[i] - cum_dp[i - (K + 1)]) % MOD
            x *= cum_prod_list[i]
        else:
            x = (cum_prod_list[i] * cum_dp[i]) % MOD
        
        ans = (b * x) % MOD
        dp[i + 1] = ans

        if i < N:
            z = (dp[i + 1] * cum_inv_prod_list[i + 1]) % MOD
            cum_dp[i + 1] = ( z + cum_dp[i]) % MOD

    return dp[- 1]    

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))


    ans1 = solve(N, K, A, B)
    ans2 = solve(N, K - 1, A, B)

    print((ans1 - ans2) % MOD)





    



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