Border

시간 제한2초메모리 제한512 MB

요약

시드로 생성된 문자열에서 i<j인 모든 쌍에 대해, i에서 시작하는 접두사와 j에서 끝나는 접미사가 일치하는 최대 길이 k의 합을 구합니다.

문제

문자열 $S[1 \ldots n]$ 이 주어진다. 부분 문자열은 $S[l \ldots r]$ 로 나타내며, $l > r$ 이면 빈 문자열이다. $f(i, j)$ 를 다음과 같이 정의한다.

$f(i, j) = \max \{k \mid 0 \leq k \leq j-i, S[i \ldots i+k-1] = S[j-k+1 \ldots j]\}$

$\sum_{1 \leq i < j \leq n} f(i, j)$ 를 출력한다.

문자열 $S$ 는 다음 방식으로 생성된다. $n$ 과 $seed$ 는 생성기의 매개변수이다.

long long seed;
for (int i = 1; i <= n; i++) {
    seed = (seed * 13331 + 23333) % 1000000007;
    s[i] = 'a' + (seed & 1);
}

첫 번째 줄에 정수 $n$ 과 $seed$ 가 주어진다 ( $1 \leq n \leq 10^6$ , $0 \leq seed \leq 10^9 + 6$ ).

답을 출력한다.