Mindenki Szereti a Permutációkat#264
Egy hosszúságú permutáció egy hosszúságú tömb, amely tartalmazza az összes egészet -től -ig, és minden eleme páronként különböző.
Anton, aki gyermekkorát tömbökkel játszva töltötte, most érdekesebb tömbök tanulmányozására tért át — permutációkra. Amikor értekezését írta, nagyon nehéz feladattal szembesült.
Adott egy hosszúságú permutáció, , és egy egész szám, . Úgy döntött, hogy létrehoz egy kétdimenziós tömböt, mérettel (k+1) \times n.
a_{0j}=j minden -re (1 \leq j \leq n);
a_{ij}=a_{(i-1)p_j} minden -re (1 \leq i \leq k) és -re (1 \leq j \leq n).
Legyen p=[5, 3, 1, 4, 2] és k=3, ekkor az alábbi tömböt kapjuk.
a_{ij} | j=1 | j=2 | j=3 | j=4 | j=5 |
i=0 | |||||
i=1 | |||||
i=2 | |||||
i=3 |
Minden -re (1 \leq x \leq n), szeretné tudni az összes olyan összegét, ahol a_{ij}=x, ahol 1 \leq i \leq k. Más szóval, szeretné megtalálni szám összegét — a szám indexeit minden a_i-ben.
Tekintsük az előző példát. Ha x=1, akkor a válasz 3+2+5=10 lesz.
Némi tanakodás és egyszerű ötletek után Anton gyorsan megoldotta ezt a problémát. Most azt szeretné tudni, hogy te is meg tudod-e oldani.
A bemenet első sorában két egész szám található, , (1 \le n \le 10^6, 1 \le k \le 10^9) — a permutáció hossza és az ismétlési műveletek száma.
A második sor tartalmazza a permutációt, (1 \le p_i \le n).
Nyomtass ki egész számot, ahol az -edik szám a x=i tartozó válasz.
Példa
1. példa
( pont): k = 1;
( pont): p_i = i;
( pont): n \le 2000, k \le 2000;
( pont): n \le 2000, bármely és esetén létezik egy , úgy hogy p[p[p \dots p[i] \dots ]]=j, ahol a beágyazottság -szor történik;
( pont): bármely és esetén létezik egy , úgy hogy p[p[p \dots p[i] \dots ]]=j, ahol a beágyazottság -szor történik;
( pont): további korlátozás nélkül.