给定一串十进制数字，我必须找到可被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;
最佳答案
这个问题可以通过线性时间 O(N)和线性空间 O(N)来解决，如果我们两个只考虑子字符串，则N为字符串的长度。我正在尝试为子序列建立算法。
要点:
1 。所有可被6整除的子字符串都可被2和3整除，我们将集中于这两个数字的可除性。
2 。这意味着所有候选子字符串必须以0或2或4或6或8结尾，以满足除以2 AND
3 。子字符串的数字总和必须可被3整除。
现在首先我们取一个长度为N的arr数组。
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到i的位数之和也可以被3整除，例如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结尾的子字符串只会对iff计数:
arr[i] == 1 and arr1[i] == 1
很明显，因为我们必须同时满足2和3的可除性。对计数的贡献为:
count = count + track[i] + 1
由于中的
j < i而添加了1track[i] = x, if there are x number of 1's in array arr1 for indices j < i.
该算法相当容易实现，将其作为练习。