Matrix Əməliyyatı#3287

Matrix Əməliyyatı

2 saniyə

64 meqabayt

Çox çətin

Siz iş axtaran bir tələbəsiniz. Bu gün bir IT şirkətinə qəbul imtahanı verdiniz. Sizdən kvadrat matris üzərində bir neçə əməliyyat yerinə yetirən səmərəli proqram yazmağınız istəndi.

Əvvəlcə sizə $N \times N$ N \times N ölçülü bir matris verilir. Sonra sizə $Q$ ədəd əməliyyat verilir. Bütün əməliyyatlar, sonuncu istisna olmaqla, matrisi dəyişir. Bütün əməliyyatları icra etdikdən sonra aşağıda izah edildiyi kimi alınan matrisin üzərində hesablama apararaq onun xəş dəyərini çıxarmalısınız.

Mövcud əməliyyatlar:

- WR r c v (Yaz): $v$ tam ədədini $(r, c)$ hüceyrəsinə yazın, yəni $A_{r, c} = v$ A_{r, c}=v təyin edin. ( $1 \leq v \leq 1, 000, 000$ 1 \le v \le 1,000,000) - CP r_1 c_1 r_2 c_2 (Kopyala): $(r_{1}, c_{1})$ (r_1, c_1) hüceyrəsindəki dəyəri $(r_{2}, c_{2})$ (r_2, c_2) hüceyrəsinə kopyalayın - SR r_1 r_2 (Sətir dəyişimi): $r_{1}$ r_1 və $r_{2}$ r_2 sətirlərini yerini dəyişin - SC c_1 c_2 (Sütun dəyişimi): $c_{1}$ c_1 və $c_{2}$ c_2 sütunlarını yerini dəyişin - RL (Sola döndərmə): Bütün matrisi $9 0^{\circ}$ 90^\circ əks istiqamətdə döndərin - RR (Sağa döndərmə): Bütün matrisi $9 0^{\circ}$ 90^\circ istiqamətində döndərin - RH (Üfüqi əks etdirmə): Sətirlərin sırasını tərsinə çevirin - RV (Şaquli əks etdirmə): Sütunların sırasını tərsinə çevirin

Giriş

Hər testin ilk sətri doqquz tam ədəd: $N$ , $Q$ , $A$ , $B$ , $C$ , $D$ , $E$ , $F$ , $G$ verir.

- $1 \leq N, Q \leq 40000$ 1 \le N, Q \le 40\,000 - $1 \leq A, B, C \leq 1, 000, 000$ 1 \le A, B, C \le 1,000,000 - $1 \leq r, c \leq N$ 1 \le r, c \le N - $A_{r, c} = (r \times A + c \times B) mod C$ A_{r,c} = (r \times A + c \times B) \bmod C — başlanğıc matrisdə $(r, c)$ mövqeyinin dəyəri - $1 \leq D \leq E \leq N$ 1 \le D \le E \le N, $1 \leq F \leq G \leq N$ 1 \le F \le G \le N, $E - D \leq 1, 000$ E-D \le 1,000, $G - F \leq 1, 000$ G-F \le 1,000

Daha sonra $Q$ sətr gəlir, hər bir sətir yuxarıdakı formatda bir əməliyyatı təsvir edir.

Çıxış

Nəticə matrisinin $B$ -dən $h$ tam xəş dəyərini aşağıdakı algoritm ilə hesablayıb çıxarın:

h <- 314159265
for r = D...E
    for c = F...G
        h <- (31 * h + B_{r,c}) mod 100000007

burada <- təyin etməni, for i = S ... T isə $i$ üçün $S$ -dən $T$ -yə kimi (hər ikisi daxil olmaqla) dövrü, və mod qalıq əməliyyatı olduğunu bildirir.

Nümunələr

Nümunə 1