有效的算法由6

鑑於十進制數字組成的字符串數整除的子序列數目，我有6有效的算法由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

下面是發現亞由3.Now整除總數檢查6 DP代碼（不完全確定它），我們還需要通過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;

來源

2016-06-06 Varun Garg

你可以粘貼一些代碼，告訴我們你到目前爲止所嘗試過的，以便我們可以幫助你。 –

您確定字符串長度可以是10⁶，或者是字符串*代表的值*限制爲那個嗎？ – trincot

@SeekAddo先生，我已經添加了我的代碼。 –

這個問題可以在線性時間內解決，O（N），和線性空間O（N），字符串的N是長度，如果我們在兩個只考慮子串。我正在嘗試構建子序列的算法。

要點：

。所有可以被6整除的子字符串都可以被2和3整除，我們將關注這兩個數字的可分性。

。這意味着所有候選子串必須以0或2或4或6或8結尾，以滿足2的整除性和

。的字符串的數字之和必須由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.

這可以在單曲遍歷輕鬆完成串。

現在我們實現了什麼是我們知道，所有的候選人都將子字符串在這樣arr[i] = 1的指數我結束了，因爲我們有由2

滿足整除現在採取另一個數組arr1，初始化爲0所有indexes.We填充它，使得

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 
}

既然說到這是數着重要組成部分，

索賠：

在指數結尾的字符串我只會有助於算當且僅當：

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

很清楚，因爲我們雙方2和3朝計數的貢獻將是滿足整除：

count = count + track[i] + 1

1在

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

的算法是非常容易實現，因爲j < i補充，採取了練習。

來源

2016-06-06 21:00:18

真的很好的解決方案。謝謝 –

@VarunGarg記住它只適用於子字符串。 –

指數（一般情況下）遞歸解決方案，如果匹配的最大值可以表示爲1e6，則轉換爲線性。

def recurse(x, substr, input): 
    if x%6 == 0: 
    print(x) 
    if len(substr) == 6: // as the value represented by string may not be > 1e6 
    return 
    if input: 
    recurse(x+input[0], substr + input[0], input[1:]) // grow the "window" 
    recurse(x, substr, input[1:]) // shift the "window" 

input = "123163736395067251284059573634848487474" 

recurse(input)

來源

2016-06-06 20:19:44 bobah

讓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，但空字符串不是一個有效的數字，因此函數返回前一箇中減去。

來源

2016-06-07 02:20:07

很好的解決方案。但是，我可以建議更改「sum」這個詞的一些用法 - 這似乎是描述了一個不同的問題（例如「123」是一個字符串「其數字和等於0模6」，但這不是什麼我們想在這裏）。 –

@j_random_hacker謝謝，你是正確的 - 修復。 –

有效的算法由6

回答

相關問題