Skip to content

11573: 【原1573】color

题目

题目描述

author: ZH 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1573

Description

有一条很长的纸带摆在你的面前,它被均分成了n个格子,从左到右编号1到n。有一个捣蛋的熊孩子看到这个纸条“熊性大发”,想要给你出个题目:他在每一个格子中写了一个数字num i,然后用m种颜色的水彩笔分别把每一个格子涂成了他喜欢的颜色color i,让你求这个纸条的总得分。

得分的定义为:选取三个递增的数x, y, z,使得它们是等差数列且第x个格子与第z个格子的颜色相同,则score = (x + z)*(num x + num z)

总得分即为所有符合条件的得分的总和。为了防止越界,只需要输出总得分除以10007所得的余数即可。

Input Format

第一行有两个整数n,m ,分别代表格子数以及颜色数。

第二行 n 个数代表每个格子中的数字{num_1,num_2,…,num_n}。 第三行 n 个数代表每个格子中的颜色{color_1,color_2,…,color_n} (1<=color_i<=m)

Output Format

共一行,一个整数,表示总得分除以10007所得的余数。。

Sample Input

6 2
5 5 3 2 2 2
2 2 1 1 2 1

Sample Output

82

Sample Explanation

纸条上分成了6个格子,上面的数字分别为5 5 3 2 2 2,且1 2 5这三个格子为一种颜色,3 4 6这三个格子为另一种颜色。那么满足条件的x y z有两组分别是1 3 5和4 5 6,得分为(1 + 5)*(5 + 2)+(4 + 6)*(2 + 2)= 42 + 40 = 82.

Sample Input

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

Sample Output

1388

Limits

  • 对于\(20\%\)的数据,1 <= n <= 100, 1 <= m <= 5。
  • 对于\(40\%\)的数据,1 <= n <= 3000, 1 <= m <= 100。
  • 对于\(100\%\)的数据,1 <= n <= 100000, 1 <= m <= 100000。其中有几组数据每种颜色出现次数不超过20次。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!