1.描述：
一条狭长的纸带被均匀划分出了nn个格子，格子编号从11到nn。每个格子上都染了一种颜色c o l o r 用[1,m]当中的一个整数表示），并且写了一个数字n u m b e r
定义一种特殊的三元组：(x,y,z)，其中x,y,z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：
1.xyz是整数 x
2.color x = color z
满足上述条件的三元组的分数规定为
整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以10,007所得的余数即可。
2. 输入：
第一行是用一个空格隔开的两个正整数n和m,n表纸带上格子的个数，m表纸带上颜色的种类数。
第二行有n用空格隔开的正整数，第i数字number表纸带上编号为i格子上面写的数字。
第三行有n用空格隔开的正整数，第i数字color表纸带上编号为i格子染的颜色。
3.输出：
一个整数，表示所求的纸带分数除以10007所得的余数。
4.样例输入：
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
5.样例输出：
1388
6.题目大意：
找所有满足关系的三元对 的 贡献和
7.思路
80分思路：
所有的三元对与中间元素没什么关系，只要首尾元素满足同奇或同偶且颜色相同即可组对，把所有满足条件元素输入便输入边处理即可
80分代码 O( n*n )
最多 1e5 种颜色 ， 同种颜色 i 奇数 放在 i * 2 - 1，偶数放在 i * 2
#include<bits/stdc++.h> using namespace std; //ios::sync_with_stdio(false); const int N = 1e6+10; typedef long long ll; int n,m; struct node{ ll num; ll n; ll col; }a[N]; const int p = 1e4+7; vector<node>ve[N]; ll sum; int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) { a[i].n=i; cin>>a[i].num; } for(int i=1;i<=n;i++) { cin>>a[i].col; if(a[i].n%2!=0) { ve[2*a[i].col-1].push_back(a[i]); int s=2*a[i].col-1; int t=ve[s].size()-1; for(int j=0;j<t;j++) { sum=(sum+((ve[s][j].n+ve[s][t].n)*(ve[s][j].num+ve[s][t].num)))%p; } } else { ve[2*a[i].col].push_back(a[i]); int s=2*a[i].col; int t=ve[s].size()-1; for(int j=0;j<t;j++) { sum=(sum+((ve[s][j].n+ve[s][t].n)*(ve[s][j].num+ve[s][t].num)))%p; } } } cout<<sum; }
复杂度 O( n2 ) 1e10，爆了
100分思路：O( n )
化简
那么不难发现，可以维护的东西出来了(有些东西是可以维护累加和(前缀和)的)，对于每种颜色的不同奇偶，我们可以维护一个
对应式子第一列
维护一个s u m x 数 组
对应式子第二列的 x的和
维护一个 s u m n 数 组
对应式子第三列的
的和
维护一个c n t 数 组
对应第四列
的个数
一百分代码
#include<bits/stdc++.h> using namespace std; //ios::sync_with_stdio(false); const int N = 3*1e5+10; typedef long long ll; int n,m; ll num[N],col; const int p = 10007; ll sumx[N]; ll sumn[N]; ll sumxn[N]; ll cnt[N]; ll sum; int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>num[i]; for(int i=1;i<=n;i++) { cin>>col; if(i%2!=0) { int s=col*2-1; sum=(sum+sumxn[s]%p+sumx[s]*num[i]%p+sumn[s]*i%p+i*num[i]*cnt[s]%p)%p; sumxn[s]=(sumxn[s]+i*num[i])%p; sumx[s]=(sumx[s]+i)%p; sumn[s]=(sumn[s]+num[i])%p; cnt[s]++; } else { int s=col*2; sum=(sum+sumxn[s]%p+sumx[s]*num[i]%p+sumn[s]*i%p+i*num[i]*cnt[s]%p)%p; sumxn[s]=(sumxn[s]+i*num[i])%p; sumx[s]=(sumx[s]+i)%p; sumn[s]=(sumn[s]+num[i])%p; cnt[s]++; } } cout<<sum; }
8.反思
一开始想出来第二种思路了，没开 long long 调了好久，还把思路又想了好几遍，没开 long long 只有四十分，从八十分到四十分，人傻了，纯纯nt，以后累加要取余的题一定要注意
1.开 long long
2.不断地 %%%%(进行取余)
3.可以用 ios::sync_with_stdio(false) 来加速，前缀和非常好的一道题
最后的最后，觉得写的还不错的，一定要点个赞留个言支持一下~~~
