P2671 求和题解

Victorique_De_Blois · 2019-01-07 13:44:39 · 题解

令Score_i表示以i为三元组第一个数的得分。

让我们来看看得分公式：

Score=(x+z)\cdot (number_x+number_z)

由乘法分配率可知:

Score=x\cdot number_x+x\cdot number_z+z\cdot number_x+z\cdot number_z

我们设可以以x,y的形式出现在同一三元组里的集合\{i\}

可得集合\{i\}的得分为：

(i1\cdot num[i1]+i1\cdot num[i2]+i2\cdot num[i1]+i2\cdot num[i3])+(i1\cdot num[i1]+i1\cdot num[i3]+i3\cdot num[i1]+i3\cdot num[i3])+...

整理可得:

Score_{i_n}=i_n\cdot \sum_{d=1}^nnumber_{i_d}+(n-2)\cdot(i_n\cdot number_{i_n})

我们把i_n提出来，就得到了如下公式：

Score_{i_n}=i_n\cdot[\sum_{d=1}^nnumber_{i_d}+(n-2)\cdot number_{i_n}]

再看题目要求：

这个分数可能会很大，你只要输出整个纸带的分数除以10,007所得的余数即可。

所以我们应该利用同余定理改写这个公式：

记住下面这个恒等式：

(\sum_{i=1}^n a_i)(mod\ M)≡\sum_{i=1}^n[a_i (mod\ m)]

设m=10007,我们有：

Score_{i_n}(mod\ m)=i_n(mod\ m)\cdot\{\sum_{d=1}^nnumber_{i_d}+[(n-2)(mod\ m)\cdot number_{i_n}+m](mod\ m)\}

由题意得：

ans=\sum_{i=1}^nScore_i

我们利用前缀和优化这个公式，可将时辅优化到O(n)

可能你对集合\{i\}的定义还不是很清楚。

特殊三元组(x,y,z)满足以下性质：

由题意得：

x<y<z
z-y=y-x
color_x=color_z

为了方便，我们设y=x+k则z=y+k

则有：

2y=x+z→(x+y)(mod\ 2)=0

~~那该三元组和y还有什么关系~~

所以我们只要满足x,z同奇偶,颜色相同，便确认他们同在集合\{i\}

前缀和优化如下：

设sum[color_i][g]表示同为颜色color_i,(mod\ 2)=g的所有数的数字和，即公式中的\sum_{d=1}^nnumber_{i_d}

再设nt[color_i][g]表示这个集合的个数，即公式中的n

一边输入颜色，就可一边累加，然后你就可以AC掉本题了。

完整代码如下：

#include <cstdio>

const int N = 100000;
const int M = 10007;
int n, m;
int sum[N + 1][2], nt[N + 1][2];
int color[N + 1], number[N + 1];
long long ans = 0;

int main()
{
    scanf(" %d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &number[i]);
        number[i] %= M;
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &color[i]);
        int c = color[i];
        int g = i % 2;
        nt[c][g]++;
        sum[c][g] += number[i];
        sum[c][g] %= M;
    }
    for(int i = 1; i <= n; i++) {
        int c = color[i];
        int g = i % 2;
        ans += i % M * ((sum[c][g] + (nt[c][g] - 2) % M * number[i] + M) % M);
        ans %= M;
    }
    printf("%lld", ans);
    return 0;
}

P2671 求和 题解

P2671 求和题解