P5598 [XR-4] Disorder Degree

Xiao X has balls of $n$ different colors. For the $i$-th color, there are $a_i$ balls. Balls of the same color are indistinguishable. Define the disorder degree $f(l, r)$ for colors $l \sim r$ as follows: line up all balls of colors $l \sim r$ in a row, and let $f(l, r)$ be the total number of distinct arrangements modulo $p$. Xiao X wants you to help compute the value of: $$ \sum_{l=1}^n \sum_{r=l}^n f(l, r) $$

The first line contains two integers $n, p$. The second line contains $n$ integers $a_i$.

Output one integer in one line, representing the answer.

[Sample 1 Explanation] $$f(1,1) = 1 \bmod 2 = 1$$ $$f(1,2) = 3 \bmod 2 = 1$$ $$f(2,2) = 1 \bmod 2 = 1$$ $$ \sum_{l=1}^n \sum_{r=l}^n f(l, r) = 3$$ --- **This problem uses bundled testdata.** - Subtask 1 (31 points): $1 \le n \le 5 \times 10^5$, $a_i$ is uniformly random in $[0, 10^5]$, time limit $1.5 \text{ s}$. - Subtask 2 (32 points): $1 \le n \le 5 \times 10^4$, time limit $5 \text{ s}$. - Subtask 3 (37 points): no special constraints, time limit $2.5 \text{ s}$. For $100\%$ of the data, $1 \le n \le 5 \times 10^5$, $0 \le a_i \le 10^{18}$, $p \in \{2,3,5,7\}$. Translated by ChatGPT 5