[Leaf] [P2671] 求和

luogu-p2671-求和">Luogu-P2671 求和

1. 核心逻辑

• 问题本质: 统计满足 color 相同且下标奇偶性相同的所有三元组 $(x, y, z)$ 的分数和。

• 破局转换:

  1. 约束拆解: $y-x=z-y \implies x+z=2y \implies x, z$ 奇偶性相同。按 (color, parity) 分组。

  2. 代数简化: 设组内元素个数为 $m$，权值为 $n_i$。求 $\sum_{i<j} (x_i + x_j)(n_i + n_j)$。

  3. 公式坍缩:

     Ans = \sum x_i \cdot [ n_i (m-1) + \sum_{j \neq i} n_j ]$$$$Ans = \sum x_i \cdot [ n_i (m-2) + \sum n_{group} ]

  4. 计算: 通过维护组内的权值总和 $O(N)$ 解决。

2. 代码实现

▶

AcCode

// P2671 [NOIP2015] 求和
// Key Logic: Grouping elements by (color, parity) + Algebraic sum simplification

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int mod = 10007;
const int maxn = 1e5 + 50;

ll num[ maxn ], col[ maxn ], cnt[ maxn ][ 2 ], sum_n[ maxn ][ 2 ];

int main( )
{
    int n, m;
    cin >> n >> m;
    for( int i = 1; i <= n; ++ i ) cin >> num[i];
    for( int i = 1; i <= n; ++ i )
    {
        cin >> col[i];
        int p = i % 2;
        cnt[ col[i] ][ p ] ++;
        sum_n[ col[i] ][ p ] = ( sum_n[ col[i] ][ p ] + num[i] ) % mod;
    }

    ll ans = 0;
    for( int i = 1; i <= n; ++ i )
    {
        int p = i % 2;
        ll c = col[i], m_cnt = cnt[ c ][ p ];
        // 核心公式：i 是当前下标，num[i] 是数字
        ll res = ( ll )i * ( ( m_cnt - 2 ) * num[i] % mod + sum_n[ c ][ p ] ) % mod;
        ans = ( ans + res ) % mod;
    }
    cout << ( ans % mod + mod ) % mod << "\n";
    return 0;
}

3. 归档备注

• 复杂度: Time $O(N)$, Space $O(N)$。

• 坑点: 模运算下减法需注意负数，cnt-2 建议加上 mod 或在最后统一处理。

• 逻辑指纹: 本题是“分组统计贡献”的经典案例。通过代数变形将 $O(N^2)$ 的枚举配对降维至 $O(N)$ 的状态维护。

• 相关知识点：降维技巧 | [[贡献法]]