c – 将可被K整除的子数组

发布时间：2020-12-16 03:19:10 所属栏目：百科来源：网络整理

导读：给定n个正整数的序列,我们需要计算其总和可被k整除的连续子序列. 约束：N高达10 ^ 6,每个元素高达10 ^ 9,K高达100 示例：设N = 5且K = 3,阵列为1 2 3 4 1 这里的答案是4 说明：存在4个子序列,其总和可以被3整除,它们是 31 21 2 32 3 4 我的尝试： long long

给定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

解决方法

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

1)使计算前缀和pref [i](对于0 <= i 这可以通过迭代所有前缀并进行计数[pref [i]％k]来完成.
最初,count [0] = 1(空前缀为0),0为i！= 0.

3)答案是所有i的总和[i] *(count [i] – 1)/ 2.

4)最好以模k计算前缀和以避免溢出.

它为什么有效？让我们仔细看看一个可被k整除的子阵列.假设它从L位置开始并以R位置结束.当且仅当pref [L – 1] == pref [R](模k)时,它可以被k整除,因为它们的差值是零模k(根据可除性的定义).因此,对于每个固定的模数,我们可以选择任何两个带有此前缀sum modulo 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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!