被3整除的子序列

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define int long long
 4 const int mod = 1e9 + 7;
 5 string s;
 6 int n,a[55],dp[510],ans;
 7 signed main(){
 8     ios::sync_with_stdio(0);
 9     cin >> s;
10     for(int i = 0; i < s.size(); i++){
11         a[i + 1] = s[i] - '0';
12         n++;
13     }
14     dp[0] = 1;
15     for(int i = 1; i <= n; i++){
16         for(int j = 500; j >= a[i]; j--){
17             dp[j] = (dp[j] + dp[j - a[i]]) % mod;
18         }
19     }
20     for(int i = 0; i <= 500; i++){
21         if(i % 3 == 0)
22             ans = (ans + dp[i]) % mod;
23     }
24     cout << ans - 1<< endl;
25     return 0;
26 }