求和(洛谷 p2671) | Axell's Blog

思路

sum+=(x+z)*(num_x+num_z)=x*num_x+z*num_x*+x*num_z+z*num_z;
对x,num_x,x*num_x前缀和处理,通过color区分颜色以及i%2区分奇偶,注意先累加后更改

代码

#include <bits/stdc++.h>
using namespace std;
long long m,n,anum[100005][2],aval[100005][2],cou[100005][2],sqrx[100005][2],arr[100005][3];  //count不能为变量,要开long long
int main(){
    cin>>m>>n;
    int p=10007;
    for (int i=1;i<=m;++i){
        scanf("%lld",&arr[i][1]);
    }
    for (int i=1;i<=m;++i){
        scanf("%lld",&arr[i][2]);
    }
    int sum=0;
    for (int i=1;i<=m;++i){
        int color=arr[i][2];
        // if (anum[color][i%2]){  //注意这里不需要判断
            sum=(sum+cou[color][i%2]*i*arr[i][1])%p;
            sum=(sum+sqrx[color][i%2])%p;
            sum=(sum+anum[color][i%2]*arr[i][1])%p;
            sum=(sum+aval[color][i%2]*i)%p;
        // }
        cou[color][i%2]++;
        sqrx[color][i%2]=(sqrx[color][i%2]+i*arr[i][1])%p;
        anum[color][i%2]=(anum[color][i%2]+i)%p;
        aval[color][i%2]=(aval[color][i%2]+arr[i][1])%p;
    }
    cout<<sum;
    return 0;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/28/