Question

Free Pascal 求解

题目描述 一条狭长的纸带被均匀划分出了 n 个格子，格子编号从 1 到 n。每个格子上都染了一种颜色colori（用[1，m]当中的一个整数表示），并且写了一个数字numberi。 定义一种特殊的三元组：(x, y, z)，其中 x，y，z 都代表纸带上格子的编号，这里的三元组要求满足以下两个条件： 1. x, y, z都是整数, x < y < z, y − x = z − y 2. colorx = colorz 满足上述条件的三元组的分数规定为(x + z) ∗ (numberx + numberz)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 10,007 所得的余数即可。 输入 第一行是用一个空格隔开的两个正整数 n 和 m，n 代表纸带上格子的个数，m 代表纸带上 颜色的种类数。 第二行有 n 个用空格隔开的正整数，第 i 个数字numberi代表纸带上编号为 i 的格子上面写的数字。 第三行有 n 个用空格隔开的正整数，第 i 个数字colori代表纸带上编号为 i 的格子染的颜色。

Answer 1

观察题意可以得知，如果第i位和第j位同色，那么就一定能够组成一个三元组，并且三元组的价值完全与中间那个数无关。
那么，我们就用一个数组存储同奇偶性的同色方块。那么价值就是(num
i+num
j)*(i+j)
现在把每组的数的下标用a1～an表示，数值用numa1～numan表示。
答案就是(numa1+numa2)*(a1+a2)+……+……
如果这样做就是O(n^2)的算法。
但是，仔细观察算式，运用乘法分配率可以得到
答案等于a1*(numa1*(n-1)+numa2+
numa3+……+numan)+
a2*(numa2*(n-1)+numa1+
numa3+……+numan)+……+
an*(numa1*+numa2+
numa3+……+numan*(n-1))
这样我们就可以用sum来表示num从a1到an的和，用sum2表示a1到an的和，答案也就是sum*sum2+(n-2)*sum2
注意mod10007