v2d

V2d

== include(page="template/taskheader" task_id="v2d") ==

Poveste şi cerinţă...

Cei $N^2^$ vrăjitori de la Universitatea Nevăzută îşi au birourile într-o matrice pătratică având latura egală cu $N$. În fiecare celulă $(i, j)$ a matricei $(0 ≤ i, j ≤ N - 1)$ se află biroul unui vrăjitor. În continuare vom identifica vrăjitorii prin coordonatele biroului lor. Vrăjitorii se află în conflict permanent, deoarece fiecare vrea să ocupe poziţia de Arhicancelar al universităţii. Acest conflict se desfăşoară pe parcursul a $T$ zile (numerotate de la $1$ la $T$).
 
În fiecare zi $z$ $(1 ≤ z ≤ T)$, fiecare vrăjitor $(i, j)$ are o putere de atac $P(z, i, j)$. Un vrăjitor $(i, j)$ atacă toţi ceilalţi $N^2^ - 1$ vrăjitori, iar puterea cu care vrăjitorul $(i, j)$ atacă un vrăjitor $(p, q)$ în ziua $z$ este $PA(z, i, j, p, q) = P(z, i, j) - dist(i, j, p, q)$. $dist(i, j, p, q)$ reprezintă distanţa dintre vrăjitorii $(i, j)$ şi $(p, q)$, şi este definită ca $|i - p| + |j - q|$. Efectul atacurilor resimţit de un vrăjitor $(p, q)$ în ziua $z$ este $Pmax(z, p, q) = max{PA(z, i, j, p, q) | (i, j) ≠ (p, q) şi 0 ≤ i, j ≤ N - 1}$. Puterea de atac a unui vrăjitor $(i, j)$ în ziua $z + 1$ va fi: $P(z + 1, i, j) = z + 1 + ((P(z, i, j) + z * Pmax(z, i, j)) modulo Q)$.
 
Fie $S$ suma valorilor $P(T + 1, i, j) (0 ≤ i, j ≤ N - 1)$. Determinaţi valoarea $(S modulo Q)$.

h2. Date de intrare

Fişierul de intrare $v2d.in$ ...

Prima linie a fişierului de intrare $v2d.in$ conţine numerele naturale $N$, $T$ şi $Q$, separate prin câte un spaţiu. Următoarele $N$ linii conţin valorile puterilor de atac ale vrăjitorilor la începutul zilei $1$. Fiecare dintre aceste linii conţine $N$ numere naturale, separate prin spaţii. Al $C$-lea număr $(1 ≤ C ≤ N)$ de pe a $L$-a $(1 ≤ L ≤ N)$ dintre aceste linii reprezintă valoarea $P(1, L - 1, C - 1)$.

h2. Date de ieşire

În fişierul de ieşire $v2d.out$ ...

În fişierul de ieşire $v2d.out$ veţi afişa suma valorilor $P(T + 1, i, j) (0 ≤ i, j ≤ N - 1)$, $modulo Q$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 500$
* $1 ≤ T ≤ 50$
* $2 ≤ Q ≤ 30 000$
* $1 ≤ P(1, i, j) ≤ Q + T$

h2. Exemplu

table(example). |_. v2d.in |_. v2d.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

table(example). |_. v2d.in |_. v2d.out |_. v2d.in |_. v2d.out |
| 3 10 10
1 2 3
4 5 6
7 8 9
| 2
|  5 50 30000
1000 900 800 700 30050
900 800 700 600 1000
800 700 600 1000 900
700 600 1000 900 800
600 1000 900 800 700
| 24385

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="v2d") ==

4793