由于n个正整数序列，我们需要计算连续的子序列的总和整除用k。

Given a sequence of n positive integers we need to count consecutive sub-sequences whose sum is divisible by k.

约束：N是高达10 ^ 6和每个元素多达10 ^ 9和K是高达100

Constraints : N is up to 10^6 and each element up to 10^9 and K is up to 100

实施例：设N = 5和K = 3和阵列是1 2 3 4 1

EXAMPLE : Let N=5 and K=3 and array be 1 2 3 4 1

下面的答案是4

说明：存在，4子序列的总和被3整除，他们是

Explanation : there exists, 4 sub-sequences whose sum is divisible by 3, they are

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

但很明显它恶劣的做法。可他们对这个问题的更好的办法？请大家帮帮忙。

But obviously its poor approach. Can their be better approach for this question? Please help.

完整问题： https://www.hackerrank.com/contests/w6 /挑战/连续-子序列

推荐答案

下面是一个快速的为O（n + k）的解决方案：

Here is a fast O(n + k) solution:

1）用于计算preFIX款项preF [I]（为0℃= I＆LT; N）

1)Lets compute prefix sums pref[i](for 0 <= i < n).

2）现在我们可以计算计数[I] - 的prefixes与总和的编号i模K（0℃= I＆所述; k）的。 这可以通过遍历所有的prefixes，使计数完成[preF（I）％K] ++。 最初，计数[0] = 1（空preFIX有一笔0）0对于i！= 0。

2)Now we can compute count[i] - the number of prefixes with sum i modulo k(0 <= i < k). This can be done by iterating over all the prefixes and making count[pref[i] % k]++. Initially, count[0] = 1(an empty prefix has sum 0) and 0 for i != 0.

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

3)The answer is sum count[i] * (count[i] - 1) / 2 for all i.

4）这是更好地计算preFIX总结模k以避免溢出。

4)It is better to compute prefix sums modulo k to avoid overflow.

为什么要工作？让我们来仔细看看一个子整除k个。比方说，它开始在与L位置，结束于R位置。这是整除用K当且仅当preF [L - 1] == preF [R]（模K），因为它们的温差为零模K（由整除的定义）。因此，对于每一个固定的模数，我们可以挑选任意两个prefixes与此preFIX总和模K（和有完全指望[我] *（计数[I] - 1）/ 2的方式来做到这一点）。

Why does it work? Let's take a closer a look at a subarray divisible by k. Let's say that it starts in L position and ends in R position. It is divisible by k if and only if pref[L - 1] == pref[R] (modulo k) because their differnce is zero modulo k(by definition of divisibility). So for each fixed modulo, we can pick any two prefixes with this prefix sum modulo k(and there are exactly count[i] * (count[i] - 1) / 2 ways to do it).

下面是我的code：

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