TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

75.0% (18/24)

Submission's AC Ratio

45.3% (208/459)

Tags

Description

「啊啊啊啊拜託你幫幫我~~~~!」(詳情請見TOIJ 1936)

你,妹可,今天也努的想成為工具人。

不過你很快就遭遇了嚴重的挫敗,就是你算不出櫻交給你的矩陣乘法。
這時你眼前出現了一個白髮蘿莉,不知道使用了甚麼黑魔法( 平板電視PBDS )在幾秒內就算出了你要花幾十分鐘的問題。
雖然猶豫了下,你很快就拋棄了羞恥心下跪乞求她的幫助。

「要我幫喔膩醬你也不是不可以喔。只是啊,喔膩醬我要你幫我一個忙~。」
「什麼忙都可以!」你完全沒有思考後果就答應了。
「嗯...好吧!那我就教你這個神奇的魔法吧!給~~」
「嗯嗯...嗯嗯...什麼!這樣怎麼可能可以這麼快!」你不可置信的說。
「不相信的話,喔膩醬可以實驗看看啊。還是喔膩醬連這種程度的魔咒能力都沒有呢(笑」
「做就做誰怕誰!對了,妳到底是誰啊?」
「我嘛~我的名字叫做雪(UKi)喔!雪.Strassen,喔膩醬要好好記得喔。」雪不知道為甚麼露出了悲傷的眼神。

「話說啊,喔膩醬剛剛很快就答應了,那,我要拿走我的報酬了喔~」
「嗯,妳想要什麼?」
「我想要你手上的限定版巧克力的領取號碼牌~」
「诶诶!這個有點...。」
「難道喔膩醬要反悔嗎?可是我已經告訴你方法了喔~」
「嗯...可是...」
「那沒辦法了,只好讓喔膩醬忘記囉~」
「你說什...麼......,怎麼突然很...想...睡......。」


「八嘎喔膩醬!人家的轉化魔法陣畫不出來啦!你快點幫人家畫啦!」不知道為甚麼,櫻又把你從床上踹了下來。
「嗯,怎麼跟今天早上一樣?」
「什麼今天早上啦!八嘎喔膩醬!人家等一下就要喔!」櫻無視你的疑問,碰的一聲把門關上就走了。但是更惡劣的是,這次櫻還加了三層的魔法結界把房間給鎖了起來。
「奇怪,怎麼又重來一次了啊!而且這次跟說好的不一樣啊!!櫻快開門啊!」
「不行...開門的話喔膩醬又會亂跑了...。」櫻在門後用有點難過的聲音說。
「嗯,櫻你說什麼?」
「八嘎喔膩醬!」櫻就這樣生氣的跑走了。

看來只能先幫櫻算出魔法陣了,但是你雖然還記得原本發生的事情,有關於魔法的部分卻怎麼想都想不起來...。
「啊,怎麼辦啊...疑,話說,那隻白髮蘿莉的名字好想有點耳熟...」

不管如何,你現在只能上了,賭上世界第一工具神的名號!

Input Format

櫻給了你很多個魔法陣,每個魔法陣都從一個整數 N 開始,代表了魔法陣的寬度。
接下有兩個寬度是 N 的魔法陣 A, B。
每個魔法陣有 N 行,每行 N 個介於 0 到 100 之間的整數。

對於所有測資, $ 1\leq N \leq 2048 $

Output Format

請輸出 N 行,每行 N 個整數用空白隔開,代表魔法陣 A B 相乘的結果。
為了怕你忘記,提醒你一下魔法陣相乘在麻瓜的世界中又稱為矩陣乘法

Sample Input 1

2
1 0
0 1
1 2
3 4

Sample Output 1

1 2
3 4

Hints

「啊!終於成功了!」你算完了櫻的魔法陣,結界也因此解開了,你走出了了房間。

「喔膩醬早啊~。」「喔膩醬喔嗨喲~。」
「疑疑~!」

你看到了夏梨坐在沙發上吃著今天最新發售的限定版巧克力,旁邊則坐著一個白髮蘿莉...。
「喔膩醬,你怎麼這麼慢啊,難道你連怎麼開門都忘記了嗎(笑」

Problem Source

果茶


2017/03/14 更新測資和範圍,調整時限和增加大測資,不好意思一開始測資太爛了QAQ
2017/03/16 再次更新時限和記憶體上限,因為題目輸入很大如果可以的話請使用整數輸入優化QAQ
2017/03/18 放寬記憶體限制,怕增加judge負擔這次就不rejudge了...

Subtasks

No. Testdata Range Score
1 0~4 10
2 5~6 90

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 2000 262144 262144 2
6 7000 262144 262144 2