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

    dp[0][(a[0]-'0')%3]=1;
    for(int i=1;i<len;i++){
        int x=(a[i]-'0')%3;
        dp[i][x]=(dp[i][x]+1)%mod;
        for(int j=0;j<3;j++){
            dp[i][j]+=(dp[i-1][j]+dp[i-1][(j+3-x)%3])%mod;
        }
    }

很明显dp[i][j]代表着第i个数除以3得到的余数j的个数。

dp[i][j]+=(dp[i-1][j]+dp[i-1][(j+3-x)%3])%mod;

这句话的意思是：当前第i个数余数j+前一个（i-1）数的余数j的个数+前一个（i-1）数的（j+3-x）%3（该数是能够与余数m相加得到余数j）

最后得到结果：

cout<<dp[len][0];

表示到达最后一个数并且能够被3整除的个数。