获得一个可被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整除的非连续子序列

回答

相关问题