Xuancheng_Mao 的小站 -QWQ-

题解：P2671 [NOIP 2015 普及组] 求和

2025.2.16 by Xuancheng_Mao

暴力：(20分)

#include<bits/stdc++.h>
using namespace std;
const int mn=1e5+5;
int n,m,number[mn],color[mn],ans;

bool check(int x,int y,int z){
    if((y-x)==(z-y) && color[x]==color[z]){
        return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>number[i];
    for(int i=1;i<=n;i++) cin>>color[i];
    for(int x=1;x<=n;x++){
        for(int y=x+1;y<=n;y++){
            for(int z=y+1;z<=n;z++){
                if(check(x,y,z)) ans+=(x+z)*(number[x]+number[z]);
                ans%=10007;
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

可以看到 $y$ 与分数无关，只要使 $(y - x) = (z - y)$ ，故 $y = (x + z) /2 = x + z /2$ 。

优化后代码（40分）：

#include<bits/stdc++.h>
using namespace std;
const int mn=1e5+5;
int n,m,number[mn],color[mn],ans;

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>number[i];
    for(int i=1;i<=n;i++) cin>>color[i];
    for(int x=1;x<=n;x++){
        for(int z=x+2;z<=n;z+=2){
            if(color[x]==color[z]) ans+=(x+z)*(number[x]+number[z]);
            ans%=10007;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

$(x + z) \times (n u mb e r_{x} + n u mb e r_{z}) = x \times n u mb e r_{x} + x \times n u mb e r_{z} + z \times n u mb e r_{x} + z \times n u mb e r_{z}$ ，如何快速计算 $x \times n u mb e r_{x} + x \times n u mb e r_{z} + z \times n u mb e r_{x} + z \times n u mb e r_{z}$ 是最大的问题。

$x / z$	2	3	4	5
1	$1 a_{1} + 1 a_{2} + 1 a_{1} + 1 a_{2}$	$1 a_{1} + 1 a_{3} + 1 a_{1} + 1 a_{3}$	$1 a_{1} + 1 a_{4} + 1 a_{1} + 1 a_{4}$	$1 a_{1} + 1 a_{5} + 1 a_{1} + 1 a_{5}$
2		$1 a_{2} + 1 a_{3} + 1 a_{2} + 1 a_{3}$	$1 a_{2} + 1 a_{4} + 1 a_{2} + 1 a_{4}$	$1 a_{2} + 1 a_{5} + 1 a_{2} + 1 a_{5}$
3			$1 a_{3} + 1 a_{4} + 1 a_{3} + 1 a_{4}$	$1 a_{3} + 1 a_{5} + 1 a_{3} + 1 a_{5}$
4				$1 a_{4} + 1 a_{5} + 1 a_{4} + 1 a_{5}$
5

( $n u mb e r_{x}$ 简化为 $a_{x}$ )

发现规律了吗？

用 $s 1$ 记录奇数颜色或偶数格子，用 $s 2$ 记录奇数颜色或偶数格子的数字之和。故 $an s_{i} = i \times ((s 2 [co l or [i]] [i %2] - n u mb er [i]) + n u mb er [i] * (s 1 [y] [i %2] - 1))$ 。

正确代码：

#include<bits/stdc++.h>
using namespace std;
const int mn=1e5+5;
int n,m,number[mn],color[mn],ans,s1[mn][2],s2[mn][2];

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>number[i];
    for(int i=1;i<=n;i++){
        cin>>color[i];
        s1[color[i]][i%2]++,s2[color[i]][i%2]=(s2[color[i]][i%2]+number[i])%10007;
    }
    for(int i=1;i<=n;i++){
        ans+=i*(s2[color[i]][i%2]+number[i]*(s1[color[i]][i%2]-2)%10007)%10007;
        ans%=10007;
    }
    cout<<ans<<'\n';
    return 0;
}

坑点：一定要记得多次取模！取模！取模！