Број сегмената чији је збир дељив са k - Решење

Груба сила

Директан начин да се задатак реши је да се угнежђеним петљама наброје сви сегменти, да се за сваки израчуна сума и да се провери да ли је дељива са \(k\), бројећи успут такве сегменте. Број је дељив са \(k\) ако и само ако даје остатак \(0\) при дељењу са \(k\), а знамо да је остатак при дељењу збира са бројем \(k\) заправо једнак збиру остатака тј. да важи да је \((a + b) \,\mathrm{mod}\,k = (a \,\mathrm{mod}\,k + b \,\mathrm{mod}\,k) \,\mathrm{mod}\,k\).

Дакле, за сваки сегмент довољно је израчунати збир по модулу \(k\), при чему за фиксирани леви крај сегмента, збир сваког наредног сегмента \([i, j]\) добијамо инкрементално, од збира сегмента \([i, j-1]\), додајући на њега број \(a_j\) и израчунавајући остатак добијеног збира при дељењу са \(k\). Збир префикса смо рачунали инкрементално, на пример, у задатку Највећи збир префикса.

#include <iostream>
#include <vector>

using namespace std;

// izracunava broj segmenata niza a ciji je zbir deljiv sa k
int brojSegmenataZbiraDeljivogSaK(const vector<int>& a, int k) {
  // duzina niza
  int n = a.size();
  // broj segmenata deljivih sa k
  int broj = 0;
  // obradjujemo sve segmente [i, j]
  for (int i = 0; i < n; i++) {
    // zbir po modulu k segmenta [i, j] inicijalizujemo na nulu
    int s = 0;
    for (int j = i; j < n; j++) {
      // azuriramo zbir po modulu k segmenta [i, j] na osnovu zbira [i, j-1]
      s = (s + a[j]) % k;
      // ako je zbir po modulu k jednak 0, zbir je deljiv sa k
      if (s == 0)
        broj++;
    }
  }
  return broj;
}


int main() {
  // ucitavamo ulazne podatke
  int k;
  cin >> k;
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  // ispisujemo broj segmenata ciji je zbir deljiv sa k
  cout << brojSegmenataZbiraDeljivogSaK(a, k) << endl;
  
  return 0;
}

Остаци збирова префикса

Тражимо број сегмената \(a_p, a_{p+1}, \ldots, a_q\), за \(0\leq p\leq q < n\), таквих да је збир \(S_{pq} = a_p + a_{p+1} + ... + a_q\) дељив са \(k\).

Обележимо са \(S_0 = 0\), \(S_1 = a_0\), \(S_2 = a_0 + a_1\), итд., тј. обележимо са \(S_i\), \(0<i\leq n\) збир првих \(i\) елемената низа (\(S_i = a_0 + a_1 + ... +a_{i-1}\)). Збир \(S_{pq}\) можемо изразити као \(S_{q+1} - S_p\). Сличну технику користили смо, на пример, у задатку Сегмент датог збира у низу целих бројева.

На основу особина операција по модулу важи да је \(S_{pq} \,\mathrm{mod}\,k = (S_{q+1} \,\mathrm{mod}\,k - S_p \,\mathrm{mod}\,k + k) \,\mathrm{mod}\,k\).

Према томе збир \(S_{pq}\) је дељив са \(k\) (тј. важи \(S_{pq} \,\mathrm{mod}\,k = 0\)) акко збирови \(S_{q+1}\) и \(S_p\) имају исти остатак при дељењу са \(k\) тј. ако је \(S_{q+1} \,\mathrm{mod}\,k = S_p\,\mathrm{mod}\,k\).

Обележимо са \(b_r\) број збирова \(S_i\) (за \(0 \leq i \leq n\)) који при дељењу са \(k\) дају остатак \(r\) (за свако \(0 \leq r < k\)). Сваки пар (различитих) збирова префикса који дају исти остатак \(r\) одређује тачно један сегмент чији је збир елемената дељив са \(k\). У скупу од \(m\) различитих елемената постоји тачно \(\frac{m(m-1)}{2}\) различитих парова. Зато је за свако \(r\) број сегмената који се добија комбинујући два збира који дају остатак \(r\) једнак \(\frac{b_r \cdot (b_r - 1)}{2}\). Према томе укупан број сегмената дељивих са \(k\) је \(\sum_{r=0}^{k-1}\frac{b_r \cdot (b_r - 1)}{2}\).

Остаје још само питање како избројати збирове префикса за сваки дати остатак тј. како израчунати све бројеве \(b_r\). Низом \(b\) дужине \(k\) памтимо број префикса чији збирови елемената дају остатке редом \(0, 1, 2, \ldots, k-1\) тако да је \(b_r\) једнак броју префикса чији збир елемената при дељењу са \(k\) даје остатак \(r\) (што је могуће, с обзиром на дату горњу границу броја \(k\)). Збирове префикса, наравно, израчунавамо инкрементално. Слично смо радили, на пример, у задатку Највећи збир префикса.

Полазни збир је \(S_0 = 0\), тако да све елементе низа \(b\) иницијализујемо на 0, осим вредности на позицији 0 коју иницијализујемо на 1. Збир текућег префикса одржавамо у променљивој \(S\) коју иницијализујемо на нулу. Учитавамо члан по члан низа \(x\), и при томе ажурирамо збир префикса (\(S\) постављамо на \((S + x)\,\mathrm{mod}\,k\)), увећавајући одговарајући бројач (вредност \(b_S\) увећавамо за 1).

i  ai Si  b0 b1 b2
      0   1  0  0
0  1  1   1  1  0
1  8  0   2  1  0
2  2  2   2  1  1
3  3  2   2  1  2
4  4  0   3  1  2

#include <iostream>
#include <vector>

using namespace std;

// izracunava broj segmenata niza a ciji je zbir deljiv sa k
int brojSegmenataZbiraDeljivogSaK(const vector<int>& a, int k) {
  // duzina niza
  int n = a.size();

  // na mestu i u nizu br čuvamo broj segmenata čiji zbir pri
  // deljenju sa k даје остатак i
  vector<int> br(k, 0);
  br[0] = 1;

  // zbir tekućeg segmenata
  int s = 0;
  for (int i = 0; i < n; i++) {
    // ažuriramo zbir elemenata tekućeg segmenta po modulu k
    s = (s + a[i]) % k;
    br[s]++;
  }

  // izračunavamo ukupan broj segmenata deljivih sa k
  int broj = 0;
  for(int i = 0; i < k; i++)
    broj += br[i]*(br[i]-1)/2;
  
  return broj;
}


int main() {
  // ucitavamo ulazne podatke
  int k;
  cin >> k;
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  // ispisujemo broj segmenata ciji je zbir deljiv sa k
  cout << brojSegmenataZbiraDeljivogSaK(a, k) << endl;
  
  return 0;
}