Be Geeks! (Editoriale)

Il numero di coppie $(i, j)$ è pari a $n \cdot (n + 1) /2$ n \cdot (n + 1) / 2 e per $n = 2 \cdot 1 0^{5}$ n = 2 \cdot 10^5 è circa $2 \cdot 1 0^{10}$ 2 \cdot 10^{10}, quindi enumerare tutti i segmenti è impossibile. Calcoliamo la somma con il metodo "divide et impera", suddividendo l'array nella posizione dell'elemento massimo.

Suddivisione nel massimo. Supponiamo di dover trovare la somma di $P (i, j)$ P(i, j) su tutti i segmenti $[i; j]$ contenuti nel segmento $[b; e]$ . Troviamo la posizione $m$ dell'elemento massimo su $[b; e]$ . Ogni segmento $[i; j] \subseteq [b; e]$ [i; j] \subseteq [b; e] appartiene esattamente a uno dei tre tipi:

contiene la posizione $m$ , cioè $b \leq i \leq m \leq j \leq e$ b \le i \le m \le j \le e;
è interamente contenuto in $[b; m - 1]$ [b; m - 1];
è interamente contenuto in $[m + 1; e]$ [m + 1; e].

I segmenti del secondo e del terzo tipo vengono elaborati ricorsivamente. Per i segmenti del primo tipo il massimo è pari ad $a_{m}$ a_m, quindi $M (i, j) = a_{m}$ M(i, j) = a_m, e il loro contributo totale è pari a

a_{m} \cdot \sum G (i, j), dove la somma e ˋ presa su tutti i b \leq i \leq m \leq j \leq e

a_m \cdot \sum G(i, j), \quad \text{dove la somma è presa su tutti i } b \le i \le m \le j \le e

Resta da calcolare rapidamente la somma dei MCD su tutti i segmenti che contengono la posizione $m$ .

Scomposizione del MCD. Un segmento $[i; j]$ che contiene $m$ è formato dalla parte sinistra $[i; m]$ e dalla parte destra $[m; j]$ . Pertanto

G (i, j) = g cd (G (i, m), G (m, j))

G(i, j) = \gcd\bigl(G(i, m), G(m, j)\bigr)

Quindi il MCD di un segmento è determinato da una coppia di valori: il MCD della parte sinistra e il MCD della parte destra.

Gruppi di estremi. Al crescere di $j$ il valore $G (m, j)$ G(m, j) non aumenta. Inoltre, ogni volta che cambia, il nuovo valore è un divisore proprio del precedente ed è quindi almeno due volte più piccolo. Di conseguenza $G (m, j)$ G(m, j) assume al più $⌊ lo g_{2} C ⌋ + 1$ \lfloor \log_2 C \rfloor + 1 valori distinti, dove $C$ è il valore massimo di un elemento. Per $C \leq 1 0^{9}$ C \le 10^9 si tratta di al più $⌊ lo g_{2} C ⌋ + 1 = 30$ \lfloor \log_2 C \rfloor + 1 = 30 valori.

Le posizioni $j$ con lo stesso valore di $G (m, j)$ G(m, j) formano un blocco contiguo. Chiamiamo un tale blocco di posizioni gruppo. Ogni gruppo è descritto da una coppia $(g, cnt)$ (g, \mathit{cnt}), dove $g$ è il valore del MCD e $cnt$ è il numero di posizioni nel gruppo. Analogamente, gli estremi sinistri $i$ vengono suddivisi in gruppi in base al valore di $G (i, m)$ .

La fine di un gruppo si trova con la ricerca binaria. Se un gruppo inizia nella posizione $j$ e $g = G (m, j)$ g = G(m, j), allora l'uguaglianza $G (m, t) = g$ G(m, t) = g vale per tutti i $t$ da $j$ fino alla fine del gruppo e non vale per tutti i $t$ successivi.

Somma sulle coppie di gruppi. Sia $(g_{L}, cnt_{L})$ (g_L, \mathit{cnt}_L) il gruppo sinistro e $(g_{R}, cnt_{R})$ (g_R, \mathit{cnt}_R) il gruppo destro. Allora tutti i $cnt_{L} \cdot cnt_{R}$ \mathit{cnt}_L \cdot \mathit{cnt}_R segmenti il cui estremo sinistro appartiene al gruppo sinistro e il cui estremo destro appartiene al gruppo destro hanno lo stesso MCD $g cd (g_{L}, g_{R})$ \gcd(g_L, g_R). Pertanto

\sum G (i, j) = \sum g cd (g_{L}, g_{R}) \cdot cnt_{L} \cdot cnt_{R},

\sum G(i, j) = \sum \gcd(g_L, g_R) \cdot \mathit{cnt}_L \cdot \mathit{cnt}_R,

dove la seconda somma è presa su tutte le coppie formate da un gruppo sinistro e un gruppo destro. Il numero di tali coppie non supera $30 \cdot 30$ 30 \cdot 30.

Query su intervallo. Per trovare la posizione del massimo e per calcolare il MCD su un segmento usiamo due sparse table. Entrambe le operazioni sono idempotenti: $max (x, x) = x$ \max(x, x) = x e $g cd (x, x) = x$ \gcd(x, x) = x. Pertanto una query su intervallo si risolve con due blocchi sovrapposti di lunghezza $2^{k}$ 2^k.

Il valore di $F (A)$ è molto grande, quindi tutti i calcoli vengono eseguiti modulo $1 0^{9} + 7$ 10^9 + 7.

Complessità. Ogni chiamata ricorsiva esclude dalla considerazione una posizione $m$ , quindi le chiamate sono al più $n$ . In ogni chiamata ci sono al più $O (lo g C)$ O(\log C) gruppi per ciascun lato. La fine di un gruppo si trova con una ricerca binaria che esegue $O (lo g n)$ O(\log n) query del MCD, e ogni query richiede $O (lo g C)$ O(\log C). L'iterazione sulle coppie di gruppi richiede $O (lo g^{2} C)$ O(\log^2 C) calcoli del MCD. La costruzione delle sparse table richiede $O (n lo g n \cdot lo g C)$ O(n \log n \cdot \log C). La complessità complessiva è $O (n lo g^{2} C \cdot (lo g n + lo g C))$ O(n \log^2 C \cdot (\log n + \log C)). In pratica i gruppi sono molto meno di $30$ e l'algoritmo è veloce.

Esempio

Consideriamo il secondo esempio: $A = (2, 4, 6, 12, 3)$ A = (2, 4, 6, 12, 3). Le posizioni sono numerate a partire da uno.

La prima chiamata elabora l'intero array $[1; 5]$ . L'elemento massimo è $a_{4} = 12$ a_4 = 12, quindi $m = 4$ m = 4. La figura mostra i gruppi degli estremi sinistri e destri.

Estremi sinistri: $G (4, 4) = 12$ G(4, 4) = 12, $G (3, 4) = g cd (6, 12) = 6$ G(3, 4) = \gcd(6, 12) = 6, $G (2, 4) = G (1, 4) = 2$ G(2, 4) = G(1, 4) = 2. Otteniamo i gruppi $(12, 1)$ , $(6, 1)$ e $(2, 2)$ .

Estremi destri: $G (4, 4) = 12$ G(4, 4) = 12, $G (4, 5) = g cd (12, 3) = 3$ G(4, 5) = \gcd(12, 3) = 3. Otteniamo i gruppi $(12, 1)$ e $(3, 1)$ .

Esaminiamo tutte le coppie di gruppi:

gruppo sinistro	gruppo destro	MCD	segmenti	contributo
(12, 1)	(12, 1)	12	1	12
(12, 1)	(3, 1)	3	1	3
(6, 1)	(12, 1)	6	1	6
(6, 1)	(3, 1)	3	1	3
(2, 2)	(12, 1)	2	2	4
(2, 2)	(3, 1)	1	2	2

La somma dei MCD sui segmenti che contengono la posizione $4$ è $12 + 3 + 6 + 3 + 4 + 2 = 30$ 12 + 3 + 6 + 3 + 4 + 2 = 30, e il contributo di questi segmenti è $12 \cdot 30 = 360$ 12 \cdot 30 = 360. Ad esempio, l'ultima riga della tabella corrisponde ai segmenti $[1; 5]$ e $[2; 5]$ : per ciascuno di essi il MCD è 1 e il massimo è 12.

Successivamente vengono elaborati ricorsivamente i segmenti $[1; 3]$ e $[5; 5]$ . Tutte le chiamate sono riportate nella tabella:

segmento	$m$	$a_{m}$ \boldsymbol{a_m}	gruppi sinistri	gruppi destri	somma MCD	contributo
$[1; 5]$ \boldsymbol{[1; 5]}	4	12	(12, 1), (6, 1), (2, 2)	(12, 1), (3, 1)	30	360
$[1; 3]$ \boldsymbol{[1; 3]}	3	6	(6, 1), (2, 2)	(6, 1)	10	60
$[1; 2]$ \boldsymbol{[1; 2]}	2	4	(4, 1), (2, 1)	(4, 1)	6	24
$[1; 1]$ \boldsymbol{[1; 1]}	1	2	(2, 1)	(2, 1)	2	4
$[5; 5]$ \boldsymbol{[5; 5]}	5	3	(3, 1)	(3, 1)	3	9

La risposta è $360 + 60 + 24 + 4 + 9 = 457$ 360 + 60 + 24 + 4 + 9 = 457.

Implementazione dell'algoritmo

Dichiariamo le costanti:

$MOD = 1 0^{9} + 7$ \mathit{MOD} = 10^9 + 7 — il modulo,
$LOG = 18$ \mathit{LOG} = 18 — l'esponente massimo nelle sparse table ( $2^{18} > 2 \cdot 1 0^{5}$ 2^{18} > 2 \cdot 10^5).

Dichiariamo il tipo ll.

#define MOD 1000000007LL
#define LOG 18 // 2^18 = 262144 > 2*10^5
typedef long long ll;

La sequenza è memorizzata nell'array $a$ ; gli elementi sono indicizzati a partire da zero. Il valore $lg2 [len]$ è pari a $⌊ lo g_{2} len ⌋$ \lfloor \log_2 \mathit{len} \rfloor. La sparse table $spMax [i] [k]$ \mathit{spMax}[i][k] memorizza l'indice dell'elemento massimo, mentre $spGcd [i] [k]$ \mathit{spGcd}[i][k] memorizza il MCD degli elementi sul segmento $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1].

vector<int> a;
vector<int> lg2;          // lg2[len] = floor(log2(len))
// spMax[i][k] — indice del massimo su [i, i + 2^k)
vector<vector<int>> spMax;
// spGcd[i][k] — MCD su [i, i + 2^k)
vector<vector<int>> spGcd;

La funzione gcd calcola il MCD di due numeri con l'algoritmo di Euclide.

int gcd(int x, int y)
{
  while (y) { int t = x % y; x = y; y = t; }
  return x;
}

La funzione better, dati due indici $i$ e $j$ , restituisce quello il cui elemento dell'array è maggiore. Se gli elementi sono uguali, restituisce $i$ .

int better(int i, int j)
{
  return a[i] >= a[j] ? i : j;
}

La funzione build riempie l'array $lg2$ e costruisce entrambe le sparse table in $O (n lo g n \cdot lo g C)$ O(n \log n \cdot \log C), $C \leq 1 0^{9}$ C \le 10^9.

void build()
{
  lg2.assign(n + 1, 0);
  for (int len = 2; len <= n; len++) lg2[len] = lg2[len / 2] + 1;
  spMax.assign(n, vector<int>(LOG + 1));
  spGcd.assign(n, vector<int>(LOG + 1));
  for (int i = 0; i < n; i++)
  {
    spMax[i][0] = i;
    spGcd[i][0] = a[i];
  }
  for (int k = 1; (1 << k) <= n; k++)
    for (int i = 0; i + (1 << k) <= n; i++)
    {
      int h = 1 << (k - 1);    // metà della lunghezza del blocco
      spMax[i][k] = better(spMax[i][k - 1], spMax[i + h][k - 1]);
      spGcd[i][k] = gcd(spGcd[i][k - 1], spGcd[i + h][k - 1]);
    }
}

C++

La funzione qMax restituisce l'indice dell'elemento massimo sul segmento $[l; r]$ [l; r].

int qMax(int l, int r)
{
  int k = lg2[r - l + 1];
  return better(spMax[l][k], spMax[r - (1 << k) + 1][k]);
}

La funzione qGcd restituisce il MCD degli elementi sul segmento $[l; r]$ [l; r]. I blocchi di lunghezza $2^{k}$ 2^k possono sovrapporsi, ma ciò non influisce sul risultato, poiché $g cd (x, x) = x$ \gcd(x, x) = x.

int qGcd(int l, int r)
{
  int k = lg2[r - l + 1];
  return gcd(spGcd[l][k], spGcd[r - (1 << k) + 1][k]);
}

La funzione lastRight trova la posizione più a destra $t \in [from; e]$ t \in [\mathit{from}; e] tale che $G (m, t) = g$ G(m, t) = g. Qui $g = G (m, from)$ g = G(m, \mathit{from}). Poiché $G (m, t)$ non aumenta al crescere di $t$ , l'uguaglianza vale su una parte iniziale del segmento $[from; e]$ , e la ricerca binaria ne trova l'ultima posizione. Il punto medio si calcola come $(lo + hi + 1) /2$ (\mathit{lo} + \mathit{hi} + 1) / 2, affinché la ricerca non si blocchi sull'assegnazione $lo = mid$ \mathit{lo} = \mathit{mid}.

int lastRight(int m, int from, int e, int g)
{
  int lo = from, hi = e;
  while (lo < hi)
  {
    int mid = (lo + hi + 1) / 2;
    if (qGcd(m, mid) == g) lo = mid; else hi = mid - 1;
  }
  return lo;
}

C++

La funzione firstLeft trova in modo simmetrico la posizione più a sinistra $t \in [b; from]$ t \in [b; \mathit{from}] tale che $G (t, m) = g$ G(t, m) = g.

int firstLeft(int m, int from, int b, int g)
{
  int lo = b, hi = from;
  while (lo < hi)
  {
    int mid = (lo + hi) / 2;
    if (qGcd(mid, m) == g) hi = mid; else lo = mid + 1;
  }
  return lo;
}

C++

La struttura Group descrive un gruppo di estremi dei segmenti:

$g$ — il valore del MCD,
$cnt$ — il numero di posizioni nel gruppo.

struct Group { int g; ll cnt; };

La funzione solve restituisce, modulo $MOD$ , la somma di $P (i, j)$ P(i, j) su tutti i segmenti $[i; j]$ contenuti in $[b; e]$ . Per un segmento vuoto la somma è $0$ .

ll solve(int b, int e)
{
  if (b > e) return 0;

Troviamo la posizione $m$ dell'elemento massimo su $[b; e]$ .

  int m = qMax(b, e);

Suddividiamo gli estremi destri $j = m, m + 1, \dots, e$ j = m, m + 1, \ldots, e in gruppi. Per il $j$ corrente calcoliamo $g = G (m, j)$ g = G(m, j) e con la funzione lastRight troviamo l'ultima posizione $t$ del gruppo. Il gruppo contiene $t - j + 1$ t - j + 1 posizioni; il gruppo successivo inizia nella posizione $t + 1$ t + 1.

  vector<Group> R;
  for (int j = m; j <= e; )
  {
    int g = qGcd(m, j);
    int t = lastRight(m, j, e, g);
    R.push_back({ g, t - j + 1 });
    j = t + 1;
  }

C++

Analogamente suddividiamo in gruppi gli estremi sinistri $i = m, m - 1, \dots, b$ i = m, m - 1, \ldots, b. Il gruppo occupa le posizioni da $t$ a $i$ e contiene $i - t + 1$ i - t + 1 posizioni; il gruppo successivo termina nella posizione $t - 1$ t - 1.

  vector<Group> L;
  for (int i = m; i >= b; )
  {
    int g = qGcd(i, m);
    int t = firstLeft(m, i, b, g);
    L.push_back({ g, i - t + 1 });
    i = t - 1;
  }

C++

Calcoliamo la somma $sumG$ dei valori del MCD su tutti i segmenti che contengono la posizione $m$ . Per ogni coppia di gruppi aggiungiamo $g cd (l . g, r . g) \cdot l . cnt \cdot r . cnt$ \gcd(l.g, r.g) \cdot l.\mathit{cnt} \cdot r.\mathit{cnt}. Il prodotto $l . cnt \cdot r . cnt$ l.\mathit{cnt} \cdot r.\mathit{cnt} non supera $4 \cdot 1 0^{10}$ 4 \cdot 10^{10} e rientra nel tipo long long. Lo riduciamo modulo $MOD$ ; dopodiché anche il prodotto del MCD (minore di $2^{30}$ 2^{30}) per un numero minore di $MOD$ rientra in long long.

  ll sumG = 0;
  for (Group &l : L)
    for (Group &r : R)
    {
      ll cnt = (l.cnt * r.cnt) % MOD;
      sumG = (sumG + gcd(l.g, r.g) % MOD * cnt) % MOD;
    }

C++

Il massimo su tutti i segmenti che contengono $m$ è pari ad $a_{m}$ a_m, quindi il loro contributo totale è $a_{m} \cdot sumG$ a_m \cdot \mathit{sumG}.

  ll res = (ll)a[m] % MOD * sumG % MOD;

Aggiungiamo le somme calcolate ricorsivamente per i segmenti situati interamente a sinistra e a destra della posizione $m$ .

  return (res + solve(b, m - 1) + solve(m + 1, e)) % MOD;
}

Parte principale del programma. Leggiamo i dati di input.

scanf("%d", &n);
a.resize(n);
for (int &x : a) scanf("%d", &x);

Costruiamo le sparse table.

build();

Stampiamo la risposta per l'intero array — il segmento $[0; n - 1]$ [0; n - 1].

printf("%lld\n", solve(0, n - 1));