题解：P10740 [SEERC2020] Divisible by 3

· · 题解

建议先做 P9753 [CSP-S 2023] 消消乐。

对序列 \{b\} 的权重进行化简：

\sum_{i=l}^{r} \sum_{j=l}^{i-1} b_i \times b_j=\sum_{i=l}^{r} b_i\sum_{j=l}^{i-1}b_j

令 s_i=\sum_{k=1}^i b_i，有：

\sum_{i=l}^{r} b_i \times (s_{i-1}-s_{l-1})

最终化简得到：

(\sum_{i=l}^{r} b_i \times s_{i-1})-s_{l-1}\times s_r+s_{l-1}^2

建议读者自行化简，接着令 u_i=\sum_{k=1}^i b_k \times s_{k-1}。

于是最终化为：u_r-u_{l-1}-s_{l-1}\times s_r+s_{l-1}^2。

该贡献可以被 3 整除，因此：

u_r \equiv u_{l-1}+s_{l-1} \times s_r -s_{l-1}^2 \pmod 3

令 l 代 l-1，最后统计答案时改变边界。

方便起见，下面将只与 l 有关的 u_l-s_{l}^2 记为 x_l。

发现上式化为：u_r \equiv s_l \times s_r +x_l \pmod 3，从小到大遍历，可以开桶统计答案。但是 s_l 的系数为 s_r，与 l 无关，无法确定其在模 3 意义下的值，因此考虑对于 s_r 在模 3 意义下的每个可能值（只有 0,1,2），每种情况单独开桶记录。

具体实现见代码注释。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,a[N],s[N],u[N],ans,t[10][10],x[N];
signed main()
{
    clock_t c1=clock();
#ifdef LOCAL
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        s[i]=(s[i-1]+a[i])%3;
        u[i]=(u[i-1]+a[i]*s[i-1])%3;
        x[i]=((u[i]-s[i]*s[i])%3+3)%3;//预处理
    }
    for(int i=0;i<=n;i++)
    {
        ans+=t[u[i]][s[i]];//第一维是容易理解的，第二维则是通过 s[r] 除以 3 的余数查询答案
  //下面对应 s[r]不同情况更新桶，第二维是 s[r] 除以 3 的余数
        t[x[i]][0]++;
        t[(s[i]+x[i])%3][1]++;
        t[(s[i]*2+x[i])%3][2]++;
    }
    cout<<ans;
#ifdef LOCAL
    cerr<<"Time used:"<<clock()-c1<<"ms";
#endif
    return 0;
}