查找n位數的子序列數，可以被8整除

Question

給定n = 1至10^5，以十進制格式存儲爲字符串。例如：如果n = 968，則在所有子序列中，即9,6,8,96,68,98,968中有3個子序列，即968,96和8，其可被8.因此，答案是3.

由於答案可能非常大，請打印答案模（10^9 + 7）。

Answer 1

這不是一個代碼寫作服務，所以我只是給你足夠的時間去做。

子序列可以有10種可能的狀態。第一種是空的。第二個是有一個領先的0.而其他8個是一個正在進行的數字是0-7 mod 8.你從字符串的開頭開始，有1種空的方式，沒有辦法做任何事情。在字符串的末尾，您的答案是具有前導0的方式的數量加上正在進行的0數字8的數字。

轉換表應該是顯而易見的。其餘的只是正常的動態編程。

Answer 2

您可以使用動態編程。令f(len, sum)爲長度爲len的前綴的子序列的數目，使得它們的和爲sum模8（sum範圍從0到7）。

f對於len = 1的值很明顯。該轉換去如下：

1. 我們可以在新的崗位開始新的序列：f(len, a[i] % 8) += 1。

2. 我們可以繼續從較短前綴的任何亞序列：

   for old_sum = 0..7 
       f(len, (old_sum * 10 + a[i]) % 8) += f(len - 1, old_sum) // take the new element 
       f(len, old_sum) += f(len - 1, old_sum) // ignore the new element 
   

當然，可以執行所有的計算模塊10^9 + 7並且使用一個標準整數類型。

1. 答案是f(n, 0)（所有元素都考慮在內，模數8爲0）。

該解決方案的時間複雜度爲O(n)（因爲存在O(n)個狀態，每個狀態都有2個轉換）。注意：如果數字不能有前導零，則可以只有一個參數指向該狀態：一個標誌，指示子序列的第一個元素是否爲零（該序列不應該擴展）。解決方案的其餘部分保持不變。

Answer 3

注意：此答案假定您的意思是連續的子序列。

的整除規則爲一個數字，以通過8整除是如果該號碼最後三個數字爲整除8.利用這一點，能夠獲得簡單O(n)算法，其中n是在數位數。

1. 設N=a_0a_1...a_(n-1)是N十進制表示與n數字。
2. 讓序列的數目迄今是s = 0
3. 對於每一組的三個數字，a_i a_(i+1) a_(i+2)，檢查數是由8整除。如果是，則將i + 1添加到序列的數目，即s = s + i。這是因爲所有字符串a_k..a_(i+2)將被8整除k，範圍從0..i。
4. Loop i from 0 to n-2-1並繼續。

所以，如果你有1424968，該子序列整除的位置：

1. i=1（424產生i+1 = 2號：424和1424）
2. i=3（496產生i+1 = 4號：496，2496， 42496，142496）
3. i=4（968得到i+1 = 5號碼：968，4968，24968，424968，1424968）

注意，一些小的修改，將需要考慮長度超過三個數字較小的數字。

因此序列總數= 2 + 4 + 5 = 11。總複雜度= O(n)其中n是位數。

Answer 4

人們可以使用任何三位數abc，遵循下面的事實：

abc % 8 = ((ab % 8) * 10 + c) % 8 

或者換句話說：該測試帶有固定開始指數一數，可級聯：

int div8(String s){ 
    int total = 0, mod = 0; 

    for(int i = 0; i < s.length(); i++) 
    { 
     mod = (mod * 10 + s.charAt(i) - '0') % 8 

     if(mod == 0) 
      total++; 
    } 

    return total; 
} 

但我們沒有固定的開始指數！ 嗯，這是很容易解決：

假設兩個序列a和b，這樣int(a) % 8 = int(b) % 8和b是a後綴。不管序列如何繼續，模塊a和b將始終保持相等。因此它是足夠的，以保持共享具有相等值的屬性的序列的數量的軌道模8

final int RESULTMOD = 1000000000 + 7; 

int div8(String s){ 
    int total = 0; 
    //modtable[i] is the number of subsequences with int(sequence) % 8 = i 
    int[] modTable = new int[8]; 

    for(int i = 0; i < s.length(); i++){ 
     int[] nextTable = new int[8]; 

     //transform table from last loop-run (shared modulo) 
     for(int j = 0; j < 8; j++){ 
      nextTable[(j * 10 + s.charAt(i) - '0') % 8] = modTable[j] % RESULTMOD; 
     } 

     //add the sequence that starts at this index to the appropriate bucket 
     nextTable[(s.charAt(i) - '0') % 8]++; 

     //add the count of all sequences with int(sequence) % 8 = 0 to the result 
     total += nextTable[0]; 
     total %= RESULTMOD; 

     //table for next run 
     modTable = nextTable; 
    } 

    return total; 
} 

運行時是O(n)。