Lista de probleme 3

Se consideră numerele naturale nenule N și D urmate de o secvență S de N numere naturale nenule ordonate crescător, indexate de la 1 la N. Să se determine numărul de cvintete de indici (i1, i2, i3, i4, i5) ce verifică relațiile:

• a • b • c = D
• a • x2 + b • y2 = c2
• a < b < c
• x ≠ y

unde am notat cu a = S[i1], b = S[i2], c = S[i3], x = S[i4], y = S[i5]. Rezultatul se va afișa modulo 1.000.000.007.

Primarul orașului tocmai a aprobat un proiect pentru construirea unui ștrand la periferia localității. Zona pe care se dorește a fi amplasat ștrandul se poate identifica cu planul 2D (infinit). Aceasta conține N arbori, aflați la coordonate întregi, cu lățimea de 1 metru. Nu există doi arbori la aceeași coordonată x sau y. Mai exact, xi ≠ xj și yi ≠ yj, pentru orice i ≠ j. Care este suma ariilor tuturor regiunilor valide posibile? Rezultatul se va afișa modulo 1.000.000.007.

Definim o expresie ca fiind un șir de caractere e care respectă una dintre următoarele:

• e = "x";
• e reprezintă un număr natural (constantă); (ex. e ∊ {"1", "2"; "200"; ...})
• e = "[e1,e2]" sau e = "(e1,e2)", unde e1, e2 sunt (sub-)expresii. Aici, (•, •) semnifică cel mai mare
  divizor comun a două numere, iar [•,•] semnifică cel mai mic multiplu comun a două numere. De exemplu, avem că (6, 8) = 2, [6, 8] = 24.

Dându-se o expresie e și două numere naturale a, b, să se calculeze eval(e, a) + eval(e, a+1) + ... + eval(e, b). Rezultatul se va afișa modulo 1.000.000.007.