题解：P10740 [SEERC 2020] Divisible by 3

· · 题解

显然意见的 DP 水题。

状态定义

设 dp[u][v] 表示在遍历到当前元素之前的所有前缀中，满足 (p1\bmod 3 = u, p2\bmod 3 = v) 的前缀个数。

转移过程

对于数组中的每个元素 x：

  1. 先取模：

    m = x \bmod 3

  2. 设处理前的前缀状态为 (u_{prev}, v_{prev})，处理后为 (u_{now}, v_{now})：

    u_{\text{now}} = (u_{\text{prev}} + [m = 1]) \bmod 3 v_{\text{now}} = (v_{\text{prev}} + [m = 2]) \bmod 3

  3. 统计所有能与当前前缀构成合法区间的前缀数量：

    \Delta = dp[u_{\text{now}}][v_{\text{now}}] + dp[u_{\text{now}}][(v_{\text{now}} - 1 + 3) \bmod 3] + dp[(u_{\text{now}} - 1 + 3) \bmod 3][v_{\text{now}}]

  4. 更新答案：

    ans = ans + \Delta

  5. 将当前前缀状态计入统计：

    dp[u_{\text{now}}][v_{\text{now}}] = dp[u_{\text{now}}][v_{\text{now}}] + 1

算法复杂度

Code

:::success[代码] 似乎很少。

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n,cnt[3][3]={{0}},p1=0,p2=0,ans=0,x;
    cin>>n;
    cnt[0][0]=1;
    for (int i=0;i<n;i++){
        cin>>x;
        if(x%3==1) p1=(p1+1)%3;
        else if(x%3==2) p2=(p2+1)%3;
        ans=ans+cnt[p1][p2]+cnt[p1][(p2-1+3)%3]+cnt[(p1-1+3)%3][p2];
        cnt[p1][p2]++;
    }
    cout<<ans<<'\n';
    return 0;
}

::: 完结散花！