1900 . 傳說中的水題
TopCoder
Tags
Description
貝塔是一個有雄心壯志的人，他苦苦鑽研各類演算法，終於在公元 20XX 年 Y 月 Z 日通過了「天下第一資料結構挑戰大賽」的重重難關，獲得「十萬序列王」的稱號，號稱通曉各類樹形結構、鍊形結構、持久化結構與各種離線法則，無所不能！
貝塔獲得這個稱號之後，變得十分狂傲，因此號稱「數論女王」的？皮決定挫挫他的銳氣，而向貝塔發出了挑戰。
？皮決定用「線性同餘」的方式產生一條長度為 $N$ 的序列 $D_{0 \ldots N-1}$，並叫貝塔依照非遞減順序排好序。但是因為排序出來的數字太多了，？皮也沒有耐心看完，而且？皮通曉傳說中的「真－？皮．轉 EX」神功，所以他只需要檢查排序結果的最前面、最中間和最後面各 $K$ 個數字，就可以知道貝塔到底有沒有真正做出來。
？皮知道貝塔對線性同餘毫不知情，為了使貝塔無法找到藉口逃避挑戰，索性把線性同餘的計算式公開：
$D_{i+1}=(D_i \times A+B)\ \%\ M $ ， $ x\ \%\ y $ 代表 $ x \div y $ 的餘數。
貝塔欣然接受了挑戰。然而他很快就發現，？皮所要求的序列長度實在太長了，他用了各種不同的方式，卻一次次地TLE、MLE。此時這題的時限和記憶體限制居然開始慢慢減少！眼看著題目愈來愈困難，走投無路的貝塔只好求助於你。
現在你有一堆？皮給的 $N, A, B, M, D_{0}$ 和 $K$。你能不能算出？皮所指定的數字，幫助貝塔獲得AC呢？
Input Format
本題有多筆測資。第一行有一個正整數 $T$，代表測資的筆數。
接下來 $T$ 行，每題有六個非負整數，依序代表 $N, A, B, M, D_{0}$ 和 $K$。
對於 1% 的測資，$A=0$。
對於 2% 的測資，$K\leq N\leq 9000$，$1\leq M\leq 1.5\times 10^ 4$。
對於 20% 的測資，$K\leq N\leq 1.5\times 10^ 5$，$1\leq M\leq 1.5\times 10^ 6$。
對於 20% 的測資，$1\leq K\leq 3$。
對於所有的測資，$T\leq 6$， $K\leq N\leq 9\times 10^ 6$， $1\leq K\leq 4000$， $1\leq M\leq 1.5\times 10^ 7$， $A, B, D_0<M$， $N\equiv K \pmod {2}$。
Output Format
請對每筆測資輸出三行，每行有以空白分隔的 $K$ 個數字，分別代表最小、最中間、最大的 $K$ 個數字。
（假設排完序的序列是$S_{0 \ldots N-1}$，則第一行是$S_{0 \ldots K-1}$，第二行是$S_{\frac{N-K}{2} \ldots \frac{N+K}{2}-1}$，第三行是$S_{N-K \ldots N-1}$。）
順帶一提，TIOJ 是不會判斷行尾空白的。
Sample Input 1
12 13 21 60 7 2
15000 2331 3292 6534 7 8
Sample Output 1
22 37
52 52
7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7
Hints
如果你想知道的話，TIOJ不是Big-Endian喔。
Problem Source
Problem set / Description by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 2 |
| 3 | 2~3 | 20 |
| 4 | 4~5 | 20 |
| 5 | 6~8 | 57 |