獲得一個可被k整除的非連續子序列

我想查找可被數字k整除的字符串的非連續子序列（比如k = 3）。我們可以把它叫做一個修改問題https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences/獲得一個可被k整除的非連續子序列

例如，輸入：

A = {1,2,3,4,1} k = 3

輸出：

9因爲12,24,21,141,123,231,1231等都是可能的

我所做的連續子序列爲

long long get_count(const vector<int> & vec, int k) { 
    vector<int> cnt_mod(k, 0); 
    cnt_mod[0] = 1; 
    int pref_sum = 0; 

    for (int elem : vec) { 
     pref_sum += elem; 
     pref_sum %= k; 
     cnt_mod[pref_sum]++; 
    } 

    long long res = 0; 
    for (int mod = 0; mod < k; mod++) 
     res += (long long)cnt_mod[mod] * (cnt_mod[mod] - 1)/2; 
    return res; 
}

您能否爲此提供一個合適的修改或新的方法（或代碼）以實現所需的目標？

謝謝:)

來源

2015-06-27 hs2202

代碼是C++，並且問題似乎沒有與Java的任何直接連接。爲什麼你的文章標籤爲'Java'？ –

我認爲12341的答案應該是9.！ –

讓DP [i] [j]：其中J表作爲模量在由數除以子序列的數目。你需要知道一些模塊算術作爲先決條件。

復發是簡單算賬：

這是專門爲3.

DP[0][(str[0]-'0')%3]=1; 
for(i=1;str[i];i++) 
    { 
     DP[i][(str[i]-'0')%3]++; 
     for(j=0;j<=2;j++) // A Modulo B is always smaller than B 
     { 
      DP[i][j] += DP[i-1][j]; 
      if(DP[i-1][j]) 
       DP[i][(j*10+str[i]-'0')%3]+=DP[i-1][j]; 
     } 
    }

首先一小塊的代碼的情況下，當我們跳過第i個信，和第二殼體形成的序列當使用第i個字母時，它給出模（j * 10 + str [i] - '0'）％3。我們可以刪除if語句

來源

2015-06-27 16:46:55

獲得一個可被k整除的非連續子序列

回答

相關問題