洛谷 P2671 求和

思路分析

直接暴力肯定是不行的，我们需要把各种相同的颜色分离出来计算。

但是只分离出来没有用，因为三元组要求中间有一个y。可以看出，x和z的奇偶性相同时，存在y使三元组成立。

所以我们用两个数组存储相同颜色的奇、偶情况，每次计算就变成计算这个序列的值。

则原式=(num[1]+num[2])*(a[num[1]]+a[num[2])+(num[1]+num[3])*(a[num[1]]+a[num[3])+(num[1]+num[4])*(a[num[1]]+a[num[4])+

　　　　...+(num[2]+num[3])*(a[num[2]]+a[num[3])+(num[2]+num[4])*(a[num[2]]+a[num[4])+

　　　　...+(num[n-1]+num[n])*(a[num[n-1]]+a[num[n])

其中，num[1]*a[num[1]]这个值被计算了n-1次，num[1]乘其他a[num[2]],a[num[3]],a[num[4]]……都为一次。

　　　num[2]*a[num[2]]这个值被计算了n-2次，num[1]乘其他a[num[1]],a[num[3]],a[num[4]]……都为一次。

以此类推。

代码

#include<iostream>

#include<vector>

#include<cmath>

using namespace std;

long long n,m,a[],ans=;

//数据比较大，用longlong

vector<long long> even[],odd[];

//使用变长数组存储

int ad(int pt)

{

    long long count=,ep=even[pt].size(),op=odd[pt].size(),s=;

    for(int i=;i<=ep;i++)

    {

        s=(s+a[even[pt][i-]])%;//所有值的总和

    }

    for(int i=;i<=ep;i++)

    {

        count+=(s%+(ep-)*(a[even[pt][i-]]%))%*even[pt][i-]%;

        count%=;

//一定要边/边%！

    }

    s=;

    for(int i=;i<=op;i++)

    {

        s=(s+a[odd[pt][i-]])%;

    }

    for(int i=;i<=op;i++)

    {

        count+=(s%+(op-)*(a[odd[pt][i-]]%))%*odd[pt][i-]%;

        count%=;

    }

    return count;

}

int main()

{

    long long cl;

    cin>>n>>m;

    for(int i=;i<=n;i++)

    {

        cin>>a[i];

    }

    for(int i=;i<=n;i++)

    {

        cin>>cl;

        if(i&)

            odd[cl].push_back(i);

        else

            even[cl].push_back(i);

    }

    for(int i=;i<=m;i++)

    {

        ans+=ad(i);

        ans%=;

    }

    cout<<ans;

}

巴特西

洛谷 P2671 求和

思路分析

代码

最新文章

热门文章