### PROBLEM LINK

**Author:** Hanlin Ren

**Tester:** Jakub Safin

**Editorialist:** Jakub Safin

### DIFFICULTY

MEDIUM

### PREREQUISITIES

counting palindromes using hashing

### PROBLEM

Count the number of odd-length palindromes in a sequence of numbers. The sequence has length N and contains K non-zero numbers, where K \ll N.

### QUICK EXPLANATION

Using direct+reverse hashes and binary search, find the largest palindrome centered at each non-zero number and between each pair of adjacent non-zero numbers. Add palindromes containing only zeroes.

### EXPLANATION

We’ve got here a variation on the classic problem of counting (or finding the longest) odd-length palindromes, which is solved by finding prefix hashes of the original sequence, reversed sequence, and binary-searching the longest palindrome centered at each index. Subtask 2 is basically this. There’s the usual caveat of choosing the right hashing method - the tests were made to fail hashing mod 2^{64}

The main complication is that the sequence is too long to even keep in memory. Fortunately, non-trivial palindromes can only be centered at very few indices. Let’s handle the following cases:

- palindromes containing only zeroes
- palidromes centered at a non-zero number
- palindromes centered at a zero, but containing a non-zero

#### Case 1

We can find all K+1 sequences (possibly empty) of consecutive zeroes. In a sequence of length L, we can find (L/2)(L/2+1) odd-length palindromes if L is even and (L+1)^2/4 if L is odd.

#### Case 2

It’s clear that if a palindrome is centered at p_c, then all non-zero numbers appearing in it form a odd-length palindromic subsequence of q centered at c. Also, p_{c+x}-p_c = p_c-p_{c-x} for all indices p_{c-x},p_{c+x} in this palindrome - therefore, we can compute a new sequence d_{1..K-1} of consecutive differences d_i=p_{i+1}-p_i, and then we need an even-length (possibly empty) palindrome in this array centered between d_{c-1} and d_c.

These two conditions are sufficient - if a substring centered at p_c contains non-zero numbers in the range [c-x,c+x] such that subsequences q_{c-x..c+x} and d_{c-x..c+x-1} are palindromic, then it is a palindrome.

We can use a modification of the usual algorithm: compute normal and reverse prefix hashes of q and d, try all c, binsearch for the largest x which gives these two palindromes, find the maximum length 2l+1 of a palindrome which doesn’t contain indices p_{c-x-1} or p_{c+x+1}, and add l+1 to the answer.

#### Case 3

Let’s consider the pair of non-zero numbers closest to the center. They need to be equal and at equal distances from the center, so they must be adjacent in seq. p - if they are p_c and p_{c+1}, then p_c+p_{c+1} must be even and the palindrome is centered at \frac{p_c+p_{c+1}}{2}.

Now we can proceed in a similar way to case 2. Palindromes in s containing [c-x,c+1+x] correspond to palindromes q_{c-x..c+1+x} and d_{c-x..c+x}.

Note that palindromes in this case are automatically distinct from all palindromes in case 2, but not in case 1. We need to subtract \frac{p_{c+1}-p_c}{2} to exclude palindromes containing only zeroes.

Case 1 takes O(K) time; in cases 2 and 3, we need to check O(K) centers and do an O(\log{K}) binary search; mrecomputing hashes takes O(K) time as well, so the total time complexity is O(K\log{K}). Memory complexity: O(K).