단어의 개수

• 에디토리얼에서 설명하는 방식은 O(26n)이지만, O(n)으로 풀이가 가능하다.
• 일반적인 서로 다른 부분 수열의 개수 는 DP를 이용해서 O(n)에 구할 수 있다.
• 이 점화식에서 S[i]==c 일때 dp값은 이렇게 바뀐다
  • dp[i] = dp[i-1] * 2 - last[c]
  • last[c] = dp[i-1] 이다
• 그러면 c가 연속으로 k번 나올 때에 어떻게 바뀌는지 규칙을 파악해보면, 다음처럼 바뀌는 것을 확인할수 있다.
  • dp[i] = dp[i-k] * (k+1) - last[c] * k
  • last[c] = dp[i-k] * k - last[c] * (k-1)
• 이제 이대로 구현하면 O(n)에 문제가 해결된다.

"""Solution code for "BOJ 24528. 단어의 개수".

- Problem link: https://www.acmicpc.net/problem/24528
- Solution link: http://www.teferi.net/ps/problems/boj/24528

Tags: [DP]
"""

import sys

MOD = 998_244_353


def main():
    N = int(sys.stdin.readline())

    count_by_last_ch = [0] * 26
    tot_count = 1
    for _ in range(N):
        c, v = sys.stdin.readline().split()

        c_ord, v = ord(c) - 97, int(v)
        count_c = count_by_last_ch[c_ord]
        tot_count, count_by_last_ch[c_ord] = (
            (tot_count * (v + 1) - count_c * v) % MOD,
            (tot_count * v - count_c * (v - 1)) % MOD,
        )

    print((tot_count - 1) % MOD)


if __name__ == '__main__':
    main()