1988 . 乘法指令 (Multiply)
TopCoder
Description
在古老的年代，電腦是以一個一個的記憶單元組成的，指令也不多。現在我們要來模擬這種電腦把兩個2位數相乘的計算過程。
我們假設這個電腦使用 $B$ 進制，以 $M$ 個記憶單元組成，編號為 $0$ 到 $M-1$ ，每個記憶單元可以儲存一個 $0$ 到 $B-1$ 的整數。以下以 $P_i$ 代表第 $i$ 個記憶單元儲存的值。
在程式執行開始之前，電腦會被植入一或兩個函數 $f_0(,f_1)$。每個函數 $f$ 接收兩個 $0$ 到 $B-1$ 的整數，輸出一個 $0$ 到 $B-1$ 的整數。這些函數是自訂的，不須符合交換律或結合律，但不能在執行過程中改變。
另外，$P_0$到$P_{B-1}$會依序被初始為$0$到$B-1$；要相乘的兩個2位數數字則會初始化在$P_B$到$P_{B+3}$：第一個數字$X=P_BB+P_{B+1}$、第二個數字$Y=P_{B+2}B+P_{B+3}$。$P_{B+4}$到$P_{M-1}$則全部初始化為0。
下圖舉例$B=3$的情況，當$X=4,Y=6$（三進位表示分別是11和20），記憶單元被初始化的情形如下圖：
這種電腦的指令只有一種：$(a,b,c,d)$，代表將$P_c$的值改變為$f_d(P_a,P_b)$。$a,b,c$可以是任何$0$到$M-1$的整數（可以重覆）；如果只有一個函數，那麼$d$將被省略，也就是指令格式為$(a,b,c)$。執行的時候，將會依序執行每一個指令。
現在，你要透過設定電腦的函數$f_i$，以及至多$S$條指令，來實現2位數的乘法。具體來說，對於所有$0 \leq X,Y < B^ 2$，在執行完所有的指令之後，必須滿足$P_{B+4} B^ 3+P_{B+5}B^ 2+P_{B+6}B+P_{B+7}=X \times Y$。除了這四個記憶單元以外，其他記憶單元的值都不影響結果的正確與否。
同樣以$B=3,X=4,Y=6$舉例，下圖為其中一種正確的執行結果（24的三進位表示是220）：
給定$B$，請寫一個程式輸出正確的函數與指令。
Input Format
本題輸入只有一行，包含一個正整數$B$，代表你要實作$B$進制的乘法自動機。
本題有許多子任務。保證存在單一方法可以完成所有子任務。
以下以$C$代表能使用的函數數量上限。
| 子任務 （測資） |
額外限制 | 分數 |
| 1 (0) | $B=3, M=10^ 5, S=10^ 5, C=1$ $X,Y$在三進位下位數只包含0或1 |
10 |
| 2 (1) | $B=5, M=10^ 5, S=10^ 5, C=1$ $X,Y< 5$ |
10 |
| 3 (2) | $B=3, M=3000, S=3000, C=2$ | 10 |
| 4 (3) | $B=7, M=3000, S=10^ 5, C=2$ | 5 |
| 5 (4) | $B=3, M=10^ 5, S=10^ 5, C=1$ | 5 |
| 6 (5) | $B=5, M=10^ 5, S=10^ 5, C=1$ | 5 |
| 7 (6) | $B=7, M=10^ 5, S=10^ 5, C=1$ | 5 |
| 8 (7) | $B=4, M=10^ 5, S=10^ 5, C=1$ | 5 |
| 9 (8) | $B=6, M=10^ 5, S=10^ 5, C=1$ | 5 |
| 10 (9) | $B=3, M=25, S=2500, C=1$ | 5 |
| 11 (10) | $B=5, M=25, S=2\times 10^ 4, C=1$ | 5 |
| 12 (11) | $B=7, M=25, S=10^ 5, C=1$ | 5 |
| 13 (12) | $B=4, M=25, S=10^ 4, C=1$ | 5 |
| 14 (13) | $B=6, M=25, S=5\times 10^ 4, C=1$ | 5 |
| 15 (14) | $B=8, M=25, S=4\times 10^ 5, C=1$ | 5 |
| 16 (15) | $B=9, M=25, S=4\times 10^ 5, C=1$ | 5 |
| 17 (16) | $B=10, M=25, S=4\times 10^ 5, C=1$ | 5 |
Output Format
第一行請輸出一個正整數$Q\leq 2$，代表你的自動機需要的函數數量。
接下來$Q\times B$行，每行輸出$B$個整數。每$B$行代表一個函數$f_a$，第$i$行第$j$個數字（$0\leq i,j<B$）代表$f_a(i,j)$的值。
接下來一行輸出一個數字$K$，代表指令數量。
接下來$K$行，如果$Q=1$，每行輸出三個非負整數$a,b,c$，代表指令為$(a,b,c)$；如果$Q=2$，每行輸出四個非負整數$a,b,c,d$，代表指令為$(a,b,c,d)$。
如果你輸出的格式不對，或值域不符合題目、子任務之限制，你會獲得一個WA。
Sample Input 1
Sample Output 1
#Sample Output 1
1
0 2 1
1 2 2
2 1 1
4
1 2 7
7 7 7
2 8 8
8 7 5
#Sample Output 2
2
0 2 1
1 2 2
2 1 0
1 2 0
2 1 0
1 1 2
3
1 2 4 0
5 5 5 1
4 2 4 1
Hints
以Sample Output 1為例，假設$X=4,Y=6$（三進位的11和20），那麼記憶單元的資訊將會以如下的方式變動：
執行結束後儲存答案的記憶單元（編號7~10）的內容是1200（也就是十進位的45），但是由於$4\times 6\neq 45$，本輸出會得到一個WA。
Problem Source
改編自CodeChef Challange 2017/07
Problem Set / Judge by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 5 |
| 5 | 4 | 5 |
| 6 | 5 | 5 |
| 7 | 6 | 5 |
| 8 | 7 | 5 |
| 9 | 8 | 5 |
| 10 | 9 | 5 |
| 11 | 10 | 5 |
| 12 | 11 | 5 |
| 13 | 12 | 5 |
| 14 | 13 | 5 |
| 15 | 14 | 5 |
| 16 | 15 | 5 |
| 17 | 16 | 5 |