妤嬌醒來,才知道剛剛的鏡花水月是一場夢。
「咦?怎麼有種舒服的感覺?」妤嬌大驚。 「歐尼醬~你終於起來了。」妹妹邊說邊動著手。
「妳...妳在做什麼啦!」妤嬌大叫。
「因為這裡沒有鬧鐘,一直叫你你也不起來。我們只好幫你做舒服的伸展運動~」 姊姊補充。
以下腦補
「話說,我們三個不是要去就妁艷嗎?」做完伸展操之後,妤嬌想起來他們原本 的目的。
「歐尼醬,我們就是發現這個才叫你趕快過來!!」妹妹一邊穿衣服一邊說。
「這是!?......,......,......,我好像在哪裡看過,應該是一艘太空船。」妤嬌經 過一陣沉思的結論。
「小艷該不會是被外星人綁架了吧?」姊姊提出一個推論。 「紅豆?」妹。
「應該是這樣沒錯,看來只能乘著這台機器去救妁艷了。」嬌。
妤嬌發現起動這台太空船必須解開一串密碼,密碼是由 m 個 n 階方陣(矩陣密碼) 和 q 對數字(詢問密碼)所組成的。 妤嬌知道解開密碼的方法是對每組詢問密碼(a,b)算出密碼值,而密碼值等於第 a 個矩陣乘第 a+1 個矩陣...乘到第 b 個矩陣,之後再取行列式值的絕對值。 妤嬌花了 0.003 秒把所有密碼值解出來了,不過如果打錯密碼值太空船就會爆炸, 所以想請你幫他驗算一下,於是你只要輸出每個密碼值%10007。
第一行含 3 個正整數 n,m,q
接下來 m 個矩陣,每個矩陣有 n 行,每行 n 個非負整數,每個非負整數的不超 過 10006
再接下來有 q 對詢問密碼,每對有兩個正整數 a,b(a≤b)
對每對詢問密碼輸出密碼值%10007
對 100%測資 n≤10, m≤10000, q≤100000,每個矩陣行列式值不為 0
對 80%測資 n≤ 5, m≤10000
對 40%測資 n≤ 5, m≤ 1000
det(A)代表對方陣 A 取行列式值
n 階方陣 M 關於元素 m(i,j)的代數餘子式記作 C(i,j)
有 C(i,j)=(-1)i+j*det(M(i,j))
M(i,j)是 M 去除掉第 i 列第 j 行的(n-1)階方陣
知 M 的行列式值=m(1,j)*C(1,j)+m(2,j)*C(2,j)+...+m(n,j)*C(n,j)( j 是一選定值)
當妤嬌啟動太空船時,他沒想到的是這台太空船只能坐一人,於是他們......。
原TIOJ1789 / problem setter: fenzhang
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 10 |
2 | 1 | 10 |
3 | 2 | 10 |
4 | 3 | 10 |
5 | 4 | 10 |
6 | 5 | 10 |
7 | 6 | 10 |
8 | 7 | 10 |
9 | 8 | 10 |
10 | 9 | 10 |