被3整除的子序列

闫氏dp分析法

1、状态表示：指的是，以结尾的对3取余后值为j的集合
2、 方案数
3、集合划分：每次转移都是从

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll ;
const ll mod = 1e9 + 7 ;
const int N = 1e3 + 10;
ll f[N][3] ;
char s[N];
int main()
{
    scanf("%s",s+1);
    int n = strlen( s + 1 );

    for( int i = 1 ; i <= n ; i ++ )
        f[i][(s[i]-'0')%3] = 1 ;
    for( int i = 1 ; i <= n ; i++ ){
        for( int j = 0 ; j < 3 ; j++ ){
            for( int k = i+1 ; k <= n ; k ++ ){
                f[k][(j+s[k]-'0')%3] = ( f[k][(j+s[k]-'0')%3] + f[i][j] ) % mod ;
            }
        }
    }
    ll ans = 0 ;
    for( int i = 1 ; i <= n ; i++ ){
        ans = ( ans + f[i][0] ) % mod ;
    }
    printf("%lld\n",ans);
    return 0;
}