Az S. 146. feladat (2020. október)

S. 146. Adott egy $\displaystyle N$ elemű $\displaystyle T$ tömb 1-től indexelve, amely nemnegatív egész számokat tartalmaz. Kétféle műveletet végzünk a $\displaystyle T$ tömb elemeivel. Az egyik műveletben hozzáadunk a tömb néhány egymást követő eleméhez egy $\displaystyle p$ értéket, vagyis adott $\displaystyle a$ és $\displaystyle b$ mellett minden $\displaystyle i\in [a,b]$ indexű $\displaystyle T[i]$ elem ezután $\displaystyle T[i]+p$ lesz. Definiáljuk adott $\displaystyle c$ és $\displaystyle d$ esetén (ahol $\displaystyle d-c+1$ páros) a következő szorzatösszeget: $\displaystyle T[c]\cdot T[c+1] + T[c+2]\cdot T[c+3] + \ldots + T[d-1]\cdot T[d]$, amely a $\displaystyle [c,d]$ intervallum értéke a $\displaystyle T$ tömbön. A második műveletben adjuk meg a $\displaystyle c$ és $\displaystyle d$ számok által meghatározott intervallum értékét. Mivel egy intervallum értéke nagyon nagy is lehet, ezért a lekérdezés eredményének $\displaystyle {10}^{9}+7$-tel vett osztási maradékát kell megadni.

Bemenet: az első sor tartalmazza az $\displaystyle N$ és $\displaystyle Q$ számokat. A következő sor $\displaystyle N$ számot tartalmaz, $\displaystyle T$ elemeit. A következő $\displaystyle Q$ sor mindegyike vagy $\displaystyle 1\ a\ b\ p$ alakú, ami azt jelenti, hogy az $\displaystyle [a;b]$ intervallumon minden tömbértéket megváltoztatunk $\displaystyle p$-vel; vagy $\displaystyle 2\ c\ d$ alakú, ami azt jelenti, hogy lekérdezzük a $\displaystyle [c,d]$ intervallum értékét.

Kimenet: minden 2-es típusú kérdésre adjuk meg az intervallum értékét modulo $\displaystyle {10}^{9}+7$.

Példa:

Korlátok: $\displaystyle 1\le N,Q\le {10}^{5}$, $\displaystyle 0\le T[i],p\le {10}^{9}$, $\displaystyle 1\le a,b,c,d\le N$, $\displaystyle a\le b$, $\displaystyle c<d$. Időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható, ha $\displaystyle N\le 100$.

Beküldendő egy s146.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2020. november 16-án LEJÁRT.

Észrevehető, hogy két féle lekérdezés lehet az intervallum kezdőpontjának paritása alapján.

Mindkét eset külön kezelhető egy-egy szegmensfával.

Részletes leírás Horcsin Bálint megoldásában:

HorcsinBalint.pdf

Statisztika:

12 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Varga 256 Péter.
6 pontot kapott:	1 versenyző.
2 pontot kapott:	7 versenyző.
1 pontot kapott:	2 versenyző.

A KöMaL 2020. októberi informatika feladatai