結果

問題 No.1845 Long Substrings
コンテスト
ユーザー LyricalMaestro
提出日時 2025-03-11 16:04:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 962 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 110,696 KB
最終ジャッジ日時 2025-03-11 16:04:18
合計ジャッジ時間 5,324 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

MOD = 10 ** 9 + 7

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

    dp = [0] * (N + 1)
    dp[0] = 1
    last_alphabet_index = [0] * 26

    first_dp = [0] * (N + 1)
    first_dp[0] = 1
    total_dp = [0] * (N + 1)
    total_dp[0] = 1
    cum_total_dp = [0] * (N + 1)
    cum_total_dp[0] = 1
    for i in range(N):
        a = S[i]

        # first_xを求める
        last = last_alphabet_index[ord(a) - ord("a")]
        x = (cum_total_dp[i] - cum_total_dp[last]) % MOD
        x += first_dp[last]
        x %= MOD

        first_dp[i + 1] = x
        total_dp[i + 1] = (x * A[i]) % MOD
        cum_total_dp[i + 1] = (cum_total_dp[i] + total_dp[i + 1]) % MOD

        last_alphabet_index[ord(a) - ord("a")] = i + 1

    answer = (cum_total_dp[N]  - cum_total_dp[0]) % MOD
    print(answer)



        







    


        

    



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