求和 (可能是这道题最详细的题解)

分析:

这哪是前缀和呀这题，这明明是数学，纯纯的数学公式推导
根据以下这两个条件:

1. $xyz$是整数, $x<y<z$, $y-x=z-y$
2. $colorx$ = $colorz$

可以很清楚的看出来实际上 $y$ 在这里根本没起作用, 只要$x+z=2y$，$colorx$ = $colorz$就行了。也就是只要$x,z$的奇偶相同，颜色相同就OK。 所以，很自然的就想到可以把奇偶和颜色分开，分别计算。
在此基础上再做优化就是数学推导，三元组规定为$(x+z)$ x $(number_x+number_z)$,把式子展开来看就是: $x$ x $number_x+x$ x $number_z+z$ x $number_x+z$ x $number_z$
在对颜色和奇偶进行分类后，对我们的每一个集合内的数来分析就有：
$(i_1+i_2)$ x $(n_{i1}+n_{i2})+(i_1+i_3)$ x $(n_{i1}+n_{i3})+......+(i_l+i_k)$ x $(n_{il}+n_{ik})+(i_2+i_3)$ x $(n_{i2}+(n_{i3}))+(i_2+i_4)$ x $n_{i2}+n_{i4}+......+(i_2+i_k)$ x $(n_{i2}+n_{ik})+......+(i_k+i_k-1)$ x $n_{ik}+n_{ik-1}$
后面再继续乘开来我们就会发现 $(k-1)$ x $(i_1$ x $n_{i1})+i_1$ x $\sum_{t=2}^k n_{it}+$一些后面的内容,请各位动动自己的聪明的脑瓜和可爱的小手自己算吧
然后$(k-1)$ x $(i_1$ x $n_i1)+i_1$ x $\sum_{t=2}^k n_{it}$就可以进一步写成$(k-2)$ x $(i_1$ x $n_i1)+i_1$ x $\sum_{t=1}^k n_{it}$这里我们终于看到了前缀和，感天动地。把后面的内容展开的话就会发现他们最后可以归成一个形式类似的式子也就是

$$(k-2) × (i_r × n_{ir})+i_r × \sum_{t-1}^k n_{it}$$

所以我们就可以先处理出前缀和和相同颜色，相同奇偶的数的个数，这样只要$O(n)$的时间复杂度就可以处理出来所有的结果了。

AC代码

#include <iostream>
using namespace std;
const int N = 100010;
const int mod = 10007;
int n,m;
int idx[N],color[N];
int cnt[N][2];
int sum[N][2];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&idx[i]);
        idx[i] = idx[i]%mod;
    }
    for(int i = 1;i <= n;i++)
    {
        int c;
        scanf("%d",&c);//输入对应的颜色
        color[i] = c;
        cnt[c][i%2]++;//该颜色对应的奇数或偶数个数加一
        sum[c][i%2] = (sum[c][i%2]+idx[i])%mod;//求前缀和
    }
    long long ans = 0;
    for(int i = 1;i <= n;i++)
    {
        int c = color[i];
        ans += i*((sum[c][i%2]+((cnt[c][i%2]-2)*idx[i]%mod+mod))%mod)%mod;//注意取模
        ans %= mod;
    }
    printf("%lld",ans);
    return 0;
}

欢迎加入团队

打公式真的好辛苦,求一个免费的赞