题解：P10740 [SEERC2020] Divisible by 3

· · 题解

思路

记 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