来源：牛客网
题目描述
一条狭长的纸带被均匀划分出了 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.color**x=colorz**
满足上述条件的三元组的分数规定为 (x+z) * (numberx+numberz) 。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 10,007 所得的余数即可。
输入描述:
第一行是用一个空格隔开的两个正整数 n 和 m,n 表纸带上格子的个数， m 表纸带上颜色的种类数。 第二行有 n 用空格隔开的正整数，第 i 数字 number 表纸带上编号为 i 格子上面写的数字。 第三行有 n 用空格隔开的正整数，第 i 数字 color 表纸带上编号为 i 格子染的颜色。
输出描述:
共一行，一个整数，表示所求的纸带分数除以10,007所得的余数。
思路：
这题主要有两个点：
- 题目要求y-x=z-y,化简即为x+z=2y，故x+z的值为偶数，易得x和z奇偶性相同，这样x和z之和才能为偶数，且颜色必须相同才能凑成一个规范的三元组；
- 分析数学规律。假设有a,b两个颜色相同的偶数格子，那么a和b就能凑成一个三元组；如果有a,b,c三个颜色相同的偶数格子，那么a和b，a和c以及b和c都能凑成三元组，这样就有三个三元组，那么根据这个规律，猜测它们的表达式之间会有某种联系。下面来推导相应的表达式：当只有a、b时，其对应的值为aa和bb，这个三元组的分数为(a+b)*(aa+bb)=0*(a*aa+b*bb)+(a+b)*(aa+bb)；当有a、b、c时，分数为(a+b)*(aa+bb)+(a+c)*(aa+cc)+(b+c)*(bb+cc)=1*(a*aa+b*bb+c*cc)+(a+b+c)*(aa+bb+cc)；当有a、b、c、d时，分数为(a+b)*(aa+bb)+(a+c)*(aa+cc)+(a+d)*(aa+dd)+(b+c)*(bb+cc)+(b+d)*(bb+dd)+(c+d)*(cc+dd)=2*(a*aa+b*bb+c*cc+d*dd)+(a+b+c+d)*(aa+bb+cc+dd)。易得表达式规律，分数=(符合条件的格子数-2)*(格子序号与格子值乘积之和)+(格子序号和)*(格子值之和)。
代码:
#include <bits/stdc++.h>
//数学题 化简计算表达式以找到对应规律
using namespace std;
const int mod =10007,N=100005;
int color[N][3][2],a[N][2],cnt[N][2];
int n,m,sum,x;
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<2;i++){
for(int j=1;j<=n;j++)scanf("%d",&a[j][i]);
}
for(int i=1;i<=n;i++){
x=i%2;
cnt[a[i][1]][x]++;
color[a[i][1]][0][x]+=i;//格子序号和
color[a[i][1]][1][x]+=a[i][0];//格子数字和
color[a[i][1]][2][x]+=1ll*i*a[i][0]%mod;//格子序号与数字乘积之和
}
for(int i=1;i<=m;i++){
for(int j=0;j<2;j++){
sum+=1ll*color[i][0][j]*color[i][1][j]%mod+1ll*(cnt[i][j]-2)*color[i][2][j]%mod;
sum%=mod;
}
}
printf("%d\n",sum);
return 0;
} 
京公网安备 11010502036488号