P2671 [NOIP 2015 Junior] Sum

NOIP 2015 Junior T3.

A long narrow strip of paper is evenly divided into $n$ cells, numbered from $1$ to $n$. Each cell is colored with a color $color_i$ (represented by an integer from $[1, m]$), and a number $number_i$ is written on it. | Index | 1 | 2 | 3 | 4 | 5 | 6 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | **Color and number** | $\color{blue}{5}$ | $\color{blue}{5}$ | $\color{red}{3}$ | $\color{red}{2}$ | $\color{blue}{2}$ | $\color{red}{2}$ | Define a special triplet $(x, y, z)$, where $x$, $y$, $z$ are indices of cells on the strip, satisfying both of the following conditions: 1. $x$, $y$, $z$ are integers, $x < y < z$, $y - x = z - y$. 2. $color_x = color_z$. The score of such a triplet is defined as $(x+z) \times (number_x+number_z)$. The score of the entire strip is the sum of the scores of all triplets that satisfy the conditions. This score can be very large; you only need to output the remainder when the total score is divided by $10007$.

The first line contains two positive integers $n$ and $m$ separated by a space. $n$ is the number of cells on the strip, and $m$ is the number of colors. The second line contains $n$ positive integers separated by spaces; the $i$-th number is the number $number_i$ written on cell $i$. The third line contains $n$ positive integers separated by spaces; the $i$-th number is the color $color_i$ of cell $i$.

A single integer, the remainder of the total score modulo $10007$.

Sample 1 Explanation. The strip is as shown in the figure in the problem description. All valid triplets are: $(1, 3, 5)$, $(4, 5, 6)$. Therefore, the total score is $(1 + 5) \times (5 + 2) + (4 + 6) \times (2 + 2) = 42 + 40 = 82$. Constraints: - For testdata groups $1$ to $2$, $1 \le n \le 100$, $1 \le m \le 5$. - For testdata groups $3$ to $4$, $1 \le n \le 3000$, $1 \le m \le 100$. - For testdata groups $5$ to $6$, $1 \le n \le 10^5$, $1 \le m \le 10^5$, and no color appears more than $20$ times. - For all $10$ testdata groups, $1 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le color_i \le m$, $1 \le number_i \le 10^5$. Translated by ChatGPT 5