前言

线性DP 也太难了吧 哈哈哈哈

思路

一开始 以为是 一层状态 $f[i]f[i]$ 表示 以当前数结尾的 总方案数 但是推方程的时候 简直无从下手

因此我们再引入一个状态 $f[i][j]f[i][j]$表示 以$S[i]S[i]$结尾的,取%后为 $JJ$的集合

这样子才可以用 $JJ$开始推嘛

因此不难想出

对于当前这个数

• 选 $f[i][j]=f[i-1][(3+(j-x))\mathrm{\%}3]f[i][j]\; =f[i-1][(3+(j-x))\backslash \%3]$ 前面的数相加 可以被3整除 例如:12 $f[i][j]=f[i][j]+1f[i][j]\; =\; f[i][j]+1$ 单独加上自己

• 不选 $f[i][j]=f[i-1][j]f[i][j]\; =f[i-1][j]$ 直接从 $i-1i-1$ 推过来

简单吧？ 哈哈哈哈哈

CODE

/**
f[i][j] 表示 以s[i]结尾对 3 取余后为j的集合
**/

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

const int N = 1e5+10;
const ll mod = 1e9+7;
ll dp[N][3];

void solve()
{
    string s ;
    cin>>s;
    s=" "+s;
    int n  = s.size();

    dp[1][(s[1]-'0')%3] = 1;

    for(int i=2;i<n;i++)
    {
        int x = (s[i]-'0')%3;
        
        for(int j = 0 ;j<=2;j++)
        {
            ///从前i-1个 和 前i-1个 和(前面相加能被整数的)
            dp[i][j] = (dp[i-1][j] + dp[i-1][(3+j-x)%3])%mod;

        }
        //只包括自己
        dp[i][x] = (dp[i][x]+1)%mod;
    }
    cout<<dp[n-1][0]%mod<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}