可被K整除的子阵列计数

Question

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

约束条件：N最多为10^6，每个元素最多为10 ^9，K最多为100

示例:设N=5，K=3，数组为1 2 3 4 1

这里的答案是4

说明：存在4个子序列，其和可被3整除，它们是：

3
1 2
1 2 3
2 3 4

我的尝试是：

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

Answer 1

这必须使您的计算更容易：

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

因此，如果max数组size=10^6并且max size of rest=99，即使您需要在简单的int32中求和所有数字，也不会有溢出。

你将花费的时间大约是O(n n)

Answer 2

这是一个快速的O（n k）解决方案：

1）让计算前缀和pref[i]（对于0

2）现在我们可以计算count[i]-和i模k的前缀数（0

3） 答案是所有i的和计数[i]*（计数[i]-1）/2。

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

为什么它能工作？让我们仔细看看一个可被k整除的子数组。假设它从L位置开始，到R位置结束。它可被k整除当且仅当pref[L-1]==pref[R]（模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;
}