高效算法,用于计算可被6整除的子序列数

Question

给定一串十进制数字,我必须找到可被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 == 2) {
               dp[i][j] += dp[i-1][(j+1)%3];
             }
        }
    }
}
long long ans = 0;
for(i=0 ; i<n ; i++) { 
    ans += dp[i][0] ;
}
return ans;

Answer 1

设SS(x, k, m)= x表示数字等于k模数的字符串的子序列数m.

SS([], k, m) = 1 if k == 0 otherwise 0   -- (see footnote at end)
SS(x + [d], k, m) = SS(x, k, m) + sum(SS(x, j, m) where j*10+d == k modulo m)

也就是说,如果向x添加一个数字,那么总和为k的子序列是x的子序列,其总和为k,加上x的子序列,其总和为j,其中(10*j)加上新数字是k模数m.

这变成了一个很好的动态程序,如果N是字符串的长度,并且m是你希望子序列被整除的数字,则在O(Nm + m ^ 2)时间运行并使用O(m)空间.对于m = 6,这是O(N)时间和O(1)空间.

# count subsequences with a sum divisible by m.
def subseq(N, m):
    a = [1] + [0] * (m - 1)
    indexes = [[j for j in xrange(m) if (10*j-i)%m == 0] for i in xrange(m)]
    for digit in N:
        a = [a[i] + sum(a[j] for j in indexes[(i - digit) % m]) for i in xrange(m)]
    return a[0] - 1

print subseq(map(int, '1232'), 6)

脚注:定义SS将空列表计为0但空字符串不是有效数字,因此函数在返回之前减去一个.

Answer 2

这个问题可以在线性时间,O(N)和线性空间O(N)中解决,如果我们两个只考虑子串,则N是字符串的长度.我正在尝试为子序列构建算法.

要点:

1.所有可被6整除的子串都可以被2和3整除,我们将通过这两个数来关注可分性.

2.这意味着所有候选子串必须以0或2或4或6或8结束,以满足2 AND的可分性

3.子串的位数之和必须可以被3整除.

现在我们首先采用一个arr长度为N 的数组.我们填充是这样的

arr[i] = 1 , if ith digit in substring is 0 or 2 or 4 or 6 or 8.

else  arr[i] = 0.

这可以通过单个遍历字符串轻松完成.

我们实现的是现在我们知道所有候选子串都将以字符串的索引i结束arr[i] = 1,因为我们必须满足2的可分性.

现在拿另一个数组arr1,为所有索引初始化为0.我们填充它

arr1[i] = 1, only if sum of digits from index 0 to index i is divisible by 3 

or from index j to i is divisible by 3, such that j < i.

else arr1[i] = 0

为了填充数组arr1,算法如下:

sum = 0
for(i = 0 to length of string - 1)
{
 sum = sum + digit at index i;
 if(sum%3 == 0)
 {
  arr1[i] = 1 
  sum = 0
 }
}

现在我们必须注意这个事实,即使从0到索引的数字之和i可以被3整除,也可能数字之和也可以从索引j到3整除i,这样就可以了0 < j < i.

为此,我们需要另一个数组,它跟踪我们到目前为止已经发现了多少个这样的子串.

让数组track如此

track[i] = x, if there are x number of 1's in array arr1 for indices j < i.

我们不需要另外遍历,我们可以修改我们以前的算法:

initialize array track to be 0 for all entries.
sum = 0
found = -1
for(i = 0 to length of string - 1)
{
 sum = sum + digit at index i;
 if(sum%3 == 0)
  {
    arr1[i] = 1 
    ++found
    track[i] = found 
    sum = 0
}

现在是计数的重要部分,

声明:

以索引i结尾的子字符串仅对countf有用:

arr[i] == 1 and arr1[i] == 1

很明显,因为我们必须满足2和3的可分性.对计数的贡献是:

count = count + track[i] + 1

因为j < iin 而添加了1

track[i] = x, if there are x number of 1's in array arr1 for indices j < i.

该算法相当容易实现,并将其作为练习.