Editing 2142 - easy sum

Sursa: [https://www.pbinfo.ro/probleme/2142/easy-sum 2142 - easy sum]
----
== Cerinţa ==
Se consideră un vector cu n elemente numere naturale. Calculați suma sumelor tuturor subsecvențelor ce se pot forma cu elementele vectorului. Pentru că suma poate fi foarte mare, afișați suma modulo 1.000.000.007.


== Date de intrare ==
Fișierul de intrare easy_sum.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.


== Date de ieșire == 
Fișierul de ieșire easy_sum.out va conține pe prima linie numărul S, reprezentând suma sumelor tuturor subsecvențelor modulo 1.000.000.007.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100.000
* numerele de pe a doua linie a fișierului de intrare vor fi cuprinse în intervalul [1,1.000.000]
* prin subsecvență înțelegem orice înșiruire de elemente din vector aflate pe poziții consecutive.
== Exemplu ==
; Intrare
: 3
: 1 2 3
; Ieșire
: 20

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 2142 - easy sum

MOD = 1000000007

def read_input():
    n = int(input())
    nums = list(map(int, input().split()))
    return n, nums

def solve(n, nums):
    # suma tuturor subsecventelor va fi data de:
    # suma(sum[i:j]) pentru i in [0, n) si j in [i+1, n+1)
    # putem rescrie asta ca:
    # suma(sum[i:n]) + suma(sum[0:j]) - suma(sum[0:i]) pentru i in [0, n) si j in [i+1, n+1)
    # (primul termen este suma tuturor subsecventelor care incep cu i, 
    #  al doilea termen este suma tuturor subsecventelor care se termina cu j-1, 
    #  iar al treilea termen este suma tuturor subsecventelor care incep inainte de i)
    # putem calcula aceste sume partial pentru a reduce timpul de executie

    # calculam suma tuturor numerelor din nums si suma partiala a numerelor din nums
    total_sum = sum(nums)
    partial_sums = [0]
    for num in nums:
        partial_sums.append((partial_sums[-1] + num) % MOD)

    # calculam suma tuturor subsecventelor
    subseq_sum = 0
    for i in range(n):
        # calculam sum[0:i] si sum[i:n]
        left_sum = partial_sums[i+1]
        right_sum = (total_sum - partial_sums[i+1] + MOD) % MOD
        
        # adaugam la suma totala suma tuturor subsecventelor care incep cu i
        subseq_sum += (i+1) * left_sum
        subseq_sum %= MOD
        
        # adaugam la suma totala suma tuturor subsecventelor care se termina cu j-1
        subseq_sum += (n-i) * right_sum
        subseq_sum %= MOD
        
        # adaugam la suma totala suma tuturor subsecventelor care incep inainte de i
        subseq_sum += left_sum * right_sum
        subseq_sum %= MOD
        
    return subseq_sum

def validate_output(expected_output, output):
    return int(expected_output) == int(output)

if __name__ == '__main__':
    n, nums = read_input()
    result = solve(n, nums)
    print(result)


</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția read_input citește datele de intrare din stdin și le returnează ca o tuplă (n, nums).
Funcția solve primește n și nums și calculează suma tuturor subsecvențelor ca descris în comentarii. În loc să calculeze suma tuturor subsecvențelor direct, calculează sume parțiale și le combină ulterior.
Funcția validate_output primește ieșirea așteptată și ieșirea obținută și returnează True dacă acestea sunt egale (ignorând spațiile suplimentare).
În if __name__ == '__main__', se citesc datele de intrare, se rezolvă