# PBinfo #4363 – sequences1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Fie un șir de întregi \( {a}_{1}, …, {a}_{k} \). Vom numi valoarea lui \( {a}_{1}, …, {a}_{k} \), pe care o vom nota \( value({a}_{1}, …, {a}_{k}) \), numărul maxim 2x astfel încât 2x divide \( {a}_{1} + … + {a}_{k} \). Spre exemplu, dacă k = 3 și a1 = 8, a2 = 3, a3 = 1 atunci a1 + a2 + a3 = 12 iar valoarea secvenței este 4.

Cerința
Vei primi o secvență de n numere naturale \( {a}_{1}, …, {a}_{n} \). Calculează restul impărțirii sumei tuturor subsecvențelor continue ale șirului \( {a}_{1}, …, {a}_{n} \) la 1.000.000.007, care este egal cu:



Cu alte cuvinte, \( S({a}_{1}, …, {a}_{n}) \) este restul împărțirii sumei valorilor \( value({a}_{i}, …, {a}_{j}) \) pentru toate 1 ≤ i ≤ j ≤ n prin împărțirea la 1.000.000.007.

Date de intrare
Programul citește de pe prima linie numărul n. A doua linie va conține întregii \( {a}_{1}, …, {a}_{n} \), separați prin câte un spațiu.

Date de ieșire
Programul va afișa o singură linie care conține numărul \( S({a}_{1}, …, {a}_{n}) \).

Restricții și precizări

1 ≤ n ≤ 200.000
1 ≤ ai ≤ 1.000.000
\( {a}_{1} + … + {a}_{n} ≤ 1.000.000 \)
Pentru 13 puncte, ai = 1, n ≤ 200
Pentru 16 puncte, \( {a}_{1} + … + {a}_{n} ≤ 200 \)
Pentru 5 puncte, n ≤ 200
Pentru 20 puncte, n ≤ 5000
Pentru 21 puncte, \( {a}_{1} + … + {a}_{n} ≤ 200.000 \)
Pentru 25 puncte, fără restricții suplimentare

Exemplul 1:
Intrare

3
1 2 3
Ieșire

8
Explicație
Valorile tuturor subsecvențelor continue sunt:


value(1) = 1
value(1, 2) = 1
value(1, 2, 3) = 2
value(2) = 2
value(2, 3) = 1
value(3) = 1

Astfel, S(1, 2, 3) este restul împărțirii sumei valorilor la 1.000.000.007, adică 8 pentru acest exemplu.

Exemplul 2:
Intrare

5
2 4 1 2 4
Ieșire

25
Explicație
Valorile tuturor subsecvențelor continue sunt:


value(2) = 2
value(2, 4) = 2
value(2, 4, 1) = 1
value(2, 4, 1, 2) = 1
value(2, 4, 1, 2, 4) = 1
value(4) = 4
value(4, 1) = 1
value(4, 1, 2) = 1
value(4, 1, 2, 4) = 1
value(1) = 1
value(1, 2) = 1
value(1, 2, 4) = 1
value(2) = 2
value(2, 4) = 2
value(4) = 4

Astfel, S(2, 4, 1, 2, 4) este restul împărțirii sumei valorilor la 1.000.000.007, adică 25 pentru acest exemplu.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
const int nmax = 3e5;
const int smax = 1e6;
int n;
int v[nmax + 5];
int fr[smax + 5];
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>v[i];
    long long sum_cnt = 0;
    long long rez = 0;
    for(int p=20;p>=0;p--)
    {
        long long sum = 0;
        long long cnt = 0;
        ++fr[0];
        for(int i=1;i<=n;i++)
        {
            sum += v[i];
            cnt += fr[sum % (1 << p)];
            ++fr[sum % (1 << p)];
        }
        cnt -= sum_cnt;
        sum_cnt += cnt;
        cnt %= Mod;
        rez += 1LL * (1 << p) * cnt % Mod;
        rez %= Mod;
        sum = 0;
        fr[0] = 0;
        for(int i=1;i<=n;i++)
        {
            sum += v[i];
            fr[sum % (1 << p)] = 0;
        }
    }
    cout<<rez<<'\n';
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4363)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4363/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4363/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)