计算可被K整除的子数组数目

Question

计算可被K整除的子数组数目

c++algorithm

8

给定一个包含n个正整数的序列，我们需要计算连续子序列的数量，其总和可被k整除。

约束条件：n最大为10^6，每个元素最大为10^9，k最大为100。

例子：当N=5，K=3且数组为1 2 3 4 1时，

答案为4。

解释：存在4个子序列，它们的总和可被3整除。

我的尝试：

long long int count=0;
for(int i=0;i<n;i++){
    long long int sum=0;
    for(int j=i;j<n;j++)
    {
        sum=sum+arr[j];
        if(sum%k==0)
        {
            count++;
        }
    }
}

但显然这是一种不好的方法。有没有更好的方法来解决这个问题？请帮忙。

完整问题：https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences

- user3786422

1

假设你的数组是[1,4,3,2,1]，那么你期望得到什么输出？你能说出来吗？ - Ayush

你的代码将无法计算所有这样的子序列。很容易看出，如果所有数字在没有第二个数字的情况下都被K整除，那么你永远不会尝试对1和3个元素进行求和而忽略2个元素。 - Arkady

@Arkady 我需要连续的子序列。 - user3786422

1

如果您对所有输入数字取%K并使用余数进行计算，那么您可以简化计算过程。这样，您将使用小于100的数字进行计算，从而避免溢出问题。 - Arkady

1

我有一个速度较慢的解决方案，它的时间复杂度是O(NK)，但更易于理解。如果您想要，我可以发布它。 - Shubham Sharma

显示剩余13条评论

2个回答

0

这将使你的计算更容易：

//Now we will move all numbers to [0..K-1]
long long int count=0;
for(int i=0;i<n;i++){
    arr[i] = arr[i]%K;
}

//Now we will calculate cout of all shortest subsequences.
long long int sum=0; 
int first(0); 
std::vector<int> beg;
std::vector<int> end;
for(int i=0;i<n;i++){
    if (arr[i] == 0)
    {
        count++; 
        continue;
    }
    sum += arr[i];
    if (sum == K)
    {
        beg.push_back(first);
        end.push_back(i);
        count++;
    }
    else
    {
        while (sum > K)
        {
            sum -= arr[first];
            first++;     
        }
        if (sum == K)
        {
            beg.push_back(first);
            end.push_back(i);
            count++;
        }
    }        
}

//this way we found all short subsequences. And we need to calculate all subsequences that consist of some short subsequencies.
int party(0);
for (int i = 0; i < beg.size() - 1; ++i)
{
    if (end[i] == beg[i+1])
    {
        count += party + 1;
        party++;
    }
    else
    {
        party = 0;
    } 
}

因此，如果最大数组大小为10^6，剩余部分的最大大小为99，则即使需要对所有数字进行简单的int32求和，也不会发生溢出。

而且你需要花费的时间大约是O(n+n)。

- Arkady

你的解决方案仍然是“O(N^2)”。 - Luchian Grigore

@Ben 不是的，请注意内部循环使用了 arr。 - Luchian Grigore

这只是优化溢出问题的想法。我还没有找到减少n^n的方法。 - Arkady

存在一个DP算法，但这个建议更适合作为评论而不是答案。 - Luchian Grigore

@LuchianGrigore，也许你是对的。但是现在我怀疑是否存在比n*n更快的算法。不过，明天我会考虑一下。这是一个有趣的任务。 - Arkady

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kraskevich · Accepted Answer

这里是一个快速的O(n + k)解决方案：

1）让我们计算前缀和 pref[i]（对于 0 <= i < n）。

2）现在我们可以计算 count[i] - 模 k 余数为 i 的前缀数量(0 <= i < k)。这可以通过遍历所有前缀并使 count[pref[i] % k]++ 来完成。最初，count[0]=1(空前缀的和为0)，对于i != 0，则为0。

3）答案是所有 i 的 sum count[i] * (count[i] - 1) / 2。

4）最好将前缀和模 k 计算以避免溢出。

它为什么有效？让我们更仔细地观察一下可被k整除的子数组。假设它从L位置开始，R位置结束。当且仅当pref[L-1] == pref[R] (模 k)时，它才是可被k整除的，因为它们的差异是零模k（根据整除的定义）。因此，对于每个固定模，我们可以选择任何两个具有该前缀和模 k 的前缀（而有确切的 count[i] * (count[i] - 1) / 2 种方法来做到这一点）。

这是我的代码：

long long get_count(const vector<int>& vec, int k) {
  //Initialize count array.
  vector<int> cnt_mod(k, 0);
  cnt_mod[0] = 1;
  int pref_sum = 0;
  //Iterate over the input sequence.
  for (int elem : vec) {
    pref_sum += elem;
    pref_sum %= k;
    cnt_mod[pref_sum]++;
  }
  //Compute the answer.
  long long res = 0;
  for (int mod = 0; mod < k; mod++)
    res += (long long)cnt_mod[mod] * (cnt_mod[mod] - 1) / 2;
  return res;
}