题意分析
对于三元组 $(x,y,z)$，显然其对于答案的贡献与 $y$ 无关，因此可以考虑消去 $y$。$y-x=z-y$ 即 $x+z=2y$，也就是说 $x,z$ 奇偶性相等。
$\text{50pts}$
$\mathcal O(n^2)$ 枚举 $x,z$，判断 $color$ 值是否相等后统计答案即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=100000,M=100000,P=10007;
int n,m,number[N+1],color[M+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",number+i);
}
for(int i=1;i<=n;i++){
scanf("%d",color+i);
}
int ans=0;
for(int l=1;l<=n;l++){
for(int r=l+2;r<=n;r+=2){
if(color[l]==color[r]){
ans=(ans+1ll*(l+r)*(number[l]+number[r]))%P;
}
}
}
printf("%d\n",ans);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
$\text{90pts}$
考虑对每一个格子按照颜色和奇偶性进行分类，枚举 $x$ 的时候枚举 $z$ 即可。
注意 $x=z$ 时不要统计，同时会重复统计，答案需要除以 $2$，模数 $10007$ 为质数，使用逆元即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=100000,M=100000,P=10007;
int n,m,number[N+1],color[M+1];
vector<int>a[M+1][2];
int qpow(int a,int n){
if(!n){
return 1;
}
int t=qpow(a,n>>1);
t=1ll*t*t%P;
if(n&1){
t=1ll*t*a%P;
}
return t;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",number+i);
}
for(int i=1;i<=n;i++){
scanf("%d",color+i);
a[color[i]][i&1].push_back(i);
}
int ans=0;
for(int l=1;l<=n;l++){
for(int r:a[color[l]][l&1]){
if(r==l){
continue;
}
ans=(ans+1ll*(l+r)*(number[l]+number[r]))%P;
}
}
printf("%d\n",1ll*ans*qpow(2,P-2)%P);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
$\text{100pts TLE}$
考虑在根据颜色、奇偶性分类后统计时先二分出 $x$ 可行的 $z$ 的左边界，减小常数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=100000,M=100000,P=10007;
int n,m,number[N+1],color[M+1];
vector<int>a[M+1][2];
int qpow(int a,int n){
if(!n){
return 1;
}
int t=qpow(a,n>>1);
t=1ll*t*t%P;
if(n&1){
t=1ll*t*a%P;
}
return t;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",number+i);
}
for(int i=1;i<=n;i++){
scanf("%d",color+i);
a[color[i]][i&1].push_back(i);
}
int ans=0;
for(int l=1;l<=n;l++){
int p=upper_bound(a[color[l]][l&1].begin(),a[color[l]][l&1].end(),l)-a[color[l]][l&1].begin();
for(int r=p;r<a[color[l]][l&1].size();r++){
ans=(ans+1ll*(l+a[color[l]][l&1][r])*(number[l]+number[a[color[l]][l&1][r]]))%P;
}
}
printf("%d\n",ans);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
$\text{100pts AC}$
考虑拆式子。
对于 $x$，令 $l,r$ 分别表示分类后数组 $pl$ 中可行 $z$ 的左右边界。
则 $x$ 对于答案的贡献为：
\(\begin{aligned} \sum_{i=l}^r[(x+pl_i)(number_x+number_{pl_i})]&=\sum_{i=l}^r[x\cdot number_x+x\cdot number_{pl_i}+pl_i\cdot number_x+pl_i\cdot number_{pl_i}]\\ &=(r-l+1)(x\cdot number_x)+x\sum_{i=l}^rnumber_{pl_i}+number_x\sum_{i=l}^rpl_i+\sum_{i=l}^rpl_i\cdot number_{pl_i} \end{aligned}\) 则对于每一个 $pl$，处理出 $number_{pl_i},pl_i,pl_i\cdot number_{pl_i}$ 的前缀和即可。
注意取模。
时间复杂度：$\mathcal O(n\log n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=100000,M=100000,P=10007;
int n,m,number[N+1],color[M+1];
struct node{
int i;
int numberSum,plSum,plNumberSum;
node(){
i=numberSum=plSum=plNumberSum=0;
}
};
bool operator <(const int &a,const node &b){
return a<b.i;
}
vector<node>a[M+1][2];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",number+i);
}
for(int i=1;i<=n;i++){
scanf("%d",color+i);
auto &pl=a[color[i]][i&1];
node x;
x.i=i;
if(pl.size()){
x.numberSum=pl.back().numberSum;
x.plSum=pl.back().plSum;
x.plNumberSum=pl.back().plNumberSum;
}
x.numberSum=(1ll*x.numberSum+number[i])%P;
x.plSum=(1ll*x.plSum+i)%P;
x.plNumberSum=(1ll*x.plNumberSum+1ll*i*number[i])%P;
pl.push_back(x);
}
int ans=0;
for(int x=1;x<=n;x++){
auto &pl=a[color[x]][x&1];
int l=upper_bound(pl.begin(),pl.end(),x)-pl.begin(),r=pl.size()-1;
int size=r-l+1;
ans=(ans+(1ll*size*x%P*number[x]%P+1ll*x*(pl[r].numberSum-pl[l-1].numberSum)%P+1ll*number[x]*(pl[r].plSum-pl[l-1].plSum)%P+1ll*(pl[r].plNumberSum-pl[l-1].plNumberSum)%P))%P;
}
printf("%d\n",(ans>0?ans:ans+P));
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
