1

我想找到可被数字 k 整除的字符串的非连续子序列（比如 k = 3）。可以将其称为对问题的修改https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences/

例如，输入：

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

输出：

9

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;
}

您能否为此提供合适的修改或新方法（或代码）以实现所需的目标？

谢谢你 ：）

4

1 回答 1

1

令 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-27T16:46:55.110 回答