求和
空间换时间，其实是一个宽泛的概念。所以这其实只是做了求和这道题目的题解。
题目大意：
n个格子，每个格子有其对应的颜色和数值。
定义一种三元组：(x,y,z)(x,y,z)(x,y,z)其中x,y,zx,y,zx,y,z都是格子上的编号，该三元组满足两个条件：
1.x,y,zx,y,zx,y,z都是整数，x<y<z,y−x=z−yx<y<z,y-x=z-yx<y<z,y−x=z−y
2.b[x]=b[z]b[x]=b[z]b[x]=b[z] (b存储颜色,即x和z的颜色相同)
满足上述条件的三元组的“分数”规定为：(x+z)∗(a[x]+a[z])(x+z)*(a[x]+a[z])(x+z)∗(a[x]+a[z])。整个纸带的分数规定为所有满足条件的三元组的“分数”之和。输出整个纸带的分数除以10007所得的余数即可。
数据范围：
1≤n≤1e51\le n \le 1e51≤n≤1e5
1≤m≤1e51\le m \le 1e51≤m≤1e5
分析：
我们一共要进行两次优化。
先说最暴力的思路：三重循环枚举x,y,zx,y,zx,y,z但是这样时间复杂度实在太高。
先研究一下第一个式子：y−x=z−yy-x=z-yy−x=z−y 将它变形成为： y=(x+z)/2y=(x+z)/2y=(x+z)/2
题目要求yyy是整数。也就是代表xxx和zzz的奇偶性一致。
在先前的条件下，如果b[x]=b[z]b[x]=b[z]b[x]=b[z]，那么有且仅有一组(x,y,z)(x,y,z)(x,y,z)。
而后我们不难发现：yyy对整个三元组没有任何决定性贡献。
所以我们可以直接把第二层枚举yyy的循环舍去。
现在的时间复杂度是O(n2)O(n^2)O(n2)。但是还不够。
如何进一步优化呢》
我们再把目光放在第二个式子上：(x+z)∗(a[x]+a[z])=xa[z]+xa[z]+za[x]+za[z](x+z)*(a[x]+a[z])=xa[z]+xa[z]+za[x]+za[z](x+z)∗(a[x]+a[z])=xa[z]+xa[z]+za[x]+za[z]
这是每一对三元组对答案的贡献。那么如何快速计算出所有三元组的贡献？
尝试简化问题：计算对于一个数列a[1],a[2],a[3],a[4],a[5]a[1],a[2],a[3],a[4],a[5]a[1],a[2],a[3],a[4],a[5]，每一对满足1≤x≤51 \le x \le 51≤x≤5的(a[x],a[z])(a[x],a[z])(a[x],a[z])，对答案都有xa[z]+xa[z]+za[x]+za[z]xa[z]+xa[z]+za[x]+za[z]xa[z]+xa[z]+za[x]+za[z]的贡献。那么贡献的综合是多少？
计算结果：对于所有系数为iii的项，有5-1个ia[i]ia[i]ia[i]和i(a[1]+a[2]+a[3]+a[4]+a[5]−a[i])i(a[1]+a[2]+a[3]+a[4]+a[5]-a[i])i(a[1]+a[2]+a[3]+a[4]+a[5]−a[i])。
对于所有统一颜色同一奇偶性的一类格子，我们都可以用这种方式计算。
使用s1s1s1数组记录某种颜色且编号为奇数或偶数格子的数目，用s2s2s2记录魔种颜色且编号为奇数或偶数格子的数字之和。对于每一个iii，对答案的贡献是i*((s2[y][i%2]-a[i])+a[i]*(s1[y][1%2]-1))。（这个式子我不知道为什么没办法用latex）
最终时间复杂度为O(n)O(n)O(n)。
代码：
这边有一个需要注意的点：减法取模。
可以注意到我对ans的增加进行了代码修改。
它原本应该是这样的：
修改前和修改后可能会被误认为是相同的。
但是因为取模之后，a[i]*(s1[b[i]][i%2])会变小。
那么本来应该是正数的添加就会变成负数。
所以需要提前移动。
