自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:00:49，当前版本为作者最后更新于2024-07-11 10:51:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

记 $f(l,r)$ 表示区间 $[l,r]$ 的权重，即：

$$F(l,r)=\sum_{i=l}^{r}\sum_{j=l}^{i-1}a_ia_j$$

发现 $F(l,r)$ 的意义为：对于每一个无序二元组 $(i,j)$，权值为 $a_ia_j$，求对于所有的 $l\leq i\lt j\leq r$，$(i,j)$ 的权值总和。

将无序二元组，转成有序二元组，并且允许 $i=j$，此时的权值总和为：

$$G(l,r)=\sum_{i=l}^{r}\sum_{j=l}^{r}a_ia_j$$

令 $f_0=0,f_i=f_{i-1}+a_i$，则可以简化为：

$$G(l,r)=(f_r-f_{l-1})^2$$

记 $g_0=0,g_i=g_{i-1}+a_1^2$，则：

$$\begin{aligned} &F(l,r)\\ &=\frac{1}{2}(G(l,r)-(g_r-g_{l-1}))\\ &=\frac{1}{2}((f_r-f_{l-1})^2-g_r+g_{l-1}) \end{aligned} $$

发现决定 $F(l,r)\bmod 3$ 是否为 $0$ 的只有 $f_r\bmod 3, f_{l-1}\bmod 3, g_r\bmod 3,g_{l-1}\bmod 3$。

我们倒序枚举 $l$ 去数 $r$（这样可以保证 $[l,r]$ 构成一个区间），记 $c_{x,y}$ 表示满足 $f_r\bmod 3=x,g_r\bmod 3=y$ 的 $r$ 数量。然后枚举 $x,y$，带入到 $F(l,r)$ 式子中看看对 $3$ 取余后是否为 $0$ 即可。注意由于 $\gcd(2,3)=1$，故 $\frac{1}{2}$ 对本题没有影响，可以删掉。

时间复杂度 $O(np^2)$，其中 $p=3$。

代码

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

const int N = 5e5 + 5;
int a[N], n, f[N], g[N], cnt[5][5], ans;

int M(int x) {return (x % 3 + 3) % 3; }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        a[i] = a[i] % 3;
        f[i] = (f[i - 1] + a[i]) % 3;
        g[i] = (g[i - 1] + a[i] * a[i]) % 3;
    }
    for(int l=n;l;l--){
        cnt[f[l]][g[l]]++;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(M((i - f[l - 1]) * (i - f[l - 1]) - j + g[l - 1]) == 0) ans += cnt[i][j];
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

// Written by xiezheyuan