小编Var*_*arg的帖子

给定一串十进制数字,我必须找到可被6整除的所有子序列的数量.

1 ? value of String ? 10^6

我已经尝试了一种天真的方法来迭代所有可能的子序列并获得答案,但这还不够快,特别是在字符串长度上有如此巨大的上限.然后我尝试了DP方法,但无法为给定范围编写DP解决方案.有人可以在这个问题上提供任何线索吗？

Sample Input
1232
Output
3
Strings Possible - 12,12,132
//Ans should be modulo 10^9 + 7

下面是DP代码(不完全确定),用于查找可被3整除的子序列的总数.现在要检查6,我们还需要将可分性结合为2,这对我来说是个问题.

for(i=0 ; i<n ; i++) {
    for(j=0 ; j<3 ; j++) {
        dp[i][j]=0 ;
    }
    int dig = (str[i]-'0')%3 ;
    dp[i][dig]++ ;
    if(i>0) {
        for(j=0 ; j<3 ; j++) {
            if(dig % 3 == 0) { 
               dp[i][j] += dp[i-1][j];
             }
            if(dig % 3 == 1) {
               dp[i][j] += dp[i-1][(j+2)%3];
             }
            if(dig % 3 == …