题解 | #被3整除的子序列#

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

const int mod = 1e9+7;

string temp;
int dp[3];
signed main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> temp;
    int len = temp.size();
    temp = " "+temp; 
    int ans = 0;
    for(int i=1;i<=len;++i){
        int cnt0=dp[0], cnt1=dp[1], cnt2=dp[2];
        ++dp[(temp[i]-'0')%3];
        dp[(temp[i]-'0'+0)%3] += cnt0;
        dp[(temp[i]-'0'+1)%3] += cnt1;
        dp[(temp[i]-'0'+2)%3] += cnt2;
        dp[0] %= mod, dp[1]%=mod, dp[2]%=mod;
    }
    cout << dp[0] << endl;
    return 0;
}