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

令$f[i][j]f[i][j]$为长度为i时模3余数为j的方案数

题目要求$f[n][0]f[n][0]$

$f[i][j]f[i][j]$由$f[i-1][j-c]f[i-1][j-c]$转移而来，c为余数

即对于当前数位有两种选择，一种是加入前面的方案中，另外是不加入之前的方案， 自成一组

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int mo=1e9+7;
#define maxm 55
ll f[maxm][3];
int main(){
    string str;
    cin>>str;
    int len=str.size();
    int c=str[0]-'0';
    f[0][c%3]=1;
    for(int i=1;i<len;i++){
        int c=str[i]-'0';
        if(c%3==0){
            f[i][0]=(f[i-1][0]+f[i-1][0])%mo;
            f[i][1]=(f[i-1][1]+f[i-1][1])%mo;
            f[i][2]=(f[i-1][2]+f[i-1][2])%mo;
        }
        else {
            f[i][0]=(f[i-1][(3-c%3)%3]+f[i-1][0])%mo;
            f[i][1]=(f[i-1][(4-c%3)%3]+f[i-1][1])%mo;
            f[i][2]=(f[i-1][(5-c%3)%3]+f[i-1][2])%mo;  
        }
        f[i][c%3]++;
    }
    cout<<f[len-1][0];
    return 0;
}