Grammarly
시간 제한2초메모리 제한512 MB
문자열 s의 서로 다른 비어 있지 않은 부분 문자열을 정점으로 하고, a의 길이가 하나 짧은 부분 문자열 b로 향하는 간선을 둔 그래프에서 s에서 시작하는 단순 경로의 개수를 998244353으로 나눈 나머지를 구한다.
문제
CauchySheep has a string s.
He looked at all its different non-empty substrings and added a directed edge from a to b if |b| + 1 = |a| and b is a substring of a.
You need to calculate the number of simple paths starting from s in this graph, modulo 998 244 353.
입력
The first line of the input contains a string s consisting of lowercase Latin letters: the string CauchySheep has (1 ≤ |s| ≤ 300 000).
출력
Output one integer: the number of simple paths starting from s in CauchySheep’s graph, modulo 998 244 353.
힌트
