求和（sum）

NOIP 2015 复赛普及组真题。本 OJ 采用标准输入输出评测，无需文件重定向。

题目描述

一条狭长的纸带被均匀划分出了n 个格子，格子编号从1 到n。每个格子上都染了一种 颜色𝑐𝑜𝑙𝑜𝑟𝑖（用[1，m]当中的一个整数表示），并且写了一个数字𝑛𝑢𝑚𝑏𝑒𝑟𝑖。

5 5 3 2 2 2 编号 1 2 3 4 5 6 定义一种特殊的三元组：(x, y, z)，其中x，y，z 都代表纸带上格子的编号，这里的三元 组要求满足以下两个条件：

1. 𝑥, 𝑦, 𝑧都是整数, 𝑥< 𝑦< 𝑧, 𝑦−𝑥= 𝑧−𝑦
2. 𝑐𝑜𝑙𝑜𝑟𝑥= 𝑐𝑜𝑙𝑜𝑟𝑧 满足上述条件的三元组的分数规定为(x + z) ∗(𝑛𝑢𝑚𝑏𝑒𝑟𝑥+ 𝑛𝑢𝑚𝑏𝑒𝑟𝑧)。整个纸带的分数 规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分 数除以10,007 所得的余数即可。

【输入格式】 输入文件名为sum.in。

第一行是用一个空格隔开的两个正整数𝑛和𝑚，𝑛代表纸带上格子的个数，𝑚代表纸带上 颜色的种类数。

第二行有𝑛个用空格隔开的正整数，第𝑖个数字𝑛𝑢𝑚𝑏𝑒𝑟𝑖代表纸带上编号为𝑖的格子上面写 的数字。

第三行有𝑛个用空格隔开的正整数，第𝑖个数字𝑐𝑜𝑙𝑜𝑟𝑖代表纸带上编号为𝑖的格子染的颜色。

【输出格式】

输出文件名为sum.out。 共一行，一个整数，表示所求的纸带分数除以10,007 所得的余数。

样例1

sum.in sum.out 6 2 5 5 3 2 2 2 2 2 1 1 2 1

82

见选手目录下的sum/sum1.in 和sum/sum1.ans。

样例1 说明

纸带如题目描述中的图所示。

所有满足条件的三元组为：(1,3, 5), (4, 5, 6)。

所以纸带的分数为(1 + 5) ∗(5 + 2) + (4 + 6) ∗(2 + 2) = 42 + 40 = 82。

----PAGE----

普及组

样例2

sum.in sum.out 15 4 5 10 8 2 2 2 9 9 7 7 5 6 4 2 4 2 2 3 3 4 3 3 2 4 4 4 4 1 1 1

1388

见选手目录下的sum/sum2.in 和sum/sum2.ans。

样例3

见选手目录下的sum/sum3.in 和sum/sum3.ans。

【数据说明】 对于第1 组至第2 组数据，1 ≤𝑛≤100, 1 ≤𝑚≤5；

对于第3 组至第4 组数据，1 ≤𝑛≤3000, 1 ≤𝑚≤100； 对于第5 组至第6 组数据，1 ≤𝑛≤100000, 1 ≤𝑚≤100000，且不存在出现次数 超过20 的颜色； 对于全部10 组数据，1 ≤𝑛≤100000, 1 ≤𝑚≤100000, 1 ≤𝑐𝑜𝑙𝑜𝑟𝑖≤𝑚, 1 ≤ 𝑛𝑢𝑚𝑏𝑒𝑟𝑖≤100000。

----PAGE----

普及组

4. 推销员 (salesman.cpp/c/pas)