TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

妤嬌醒來,才知道剛剛的鏡花水月是一場夢。
「咦?怎麼有種舒服的感覺?」妤嬌大驚。 「歐尼醬~你終於起來了。」妹妹邊說邊動著手。
「妳...妳在做什麼啦!」妤嬌大叫。
「因為這裡沒有鬧鐘,一直叫你你也不起來。我們只好幫你做舒服的伸展運動~」 姊姊補充。
以下腦補
「話說,我們三個不是要去就妁艷嗎?」做完伸展操之後,妤嬌想起來他們原本 的目的。
「歐尼醬,我們就是發現這個才叫你趕快過來!!」妹妹一邊穿衣服一邊說。

「這是!?......,......,......,我好像在哪裡看過,應該是一艘太空船。」妤嬌經 過一陣沉思的結論。
「小艷該不會是被外星人綁架了吧?」姊姊提出一個推論。 「紅豆?」妹。
「應該是這樣沒錯,看來只能乘著這台機器去救妁艷了。」嬌。
妤嬌發現起動這台太空船必須解開一串密碼,密碼是由 m 個 n 階方陣(矩陣密碼) 和 q 對數字(詢問密碼)所組成的。 妤嬌知道解開密碼的方法是對每組詢問密碼(a,b)算出密碼值,而密碼值等於第 a 個矩陣乘第 a+1 個矩陣...乘到第 b 個矩陣,之後再取行列式值的絕對值。 妤嬌花了 0.003 秒把所有密碼值解出來了,不過如果打錯密碼值太空船就會爆炸, 所以想請你幫他驗算一下,於是你只要輸出每個密碼值%10007。

Input Format

第一行含 3 個正整數 n,m,q
接下來 m 個矩陣,每個矩陣有 n 行,每行 n 個非負整數,每個非負整數的不超 過 10006
再接下來有 q 對詢問密碼,每對有兩個正整數 a,b(a≤b)

Output Format

對每對詢問密碼輸出密碼值%10007

Sample Input

4 3 4
1 2 3 4
4 3 2 1
2 4 7 9
9 7 5 4
4 1 1 1
1 4 1 2
1 1 4 3
1 1 1 4
9 9 9 9
0 9 9 9
0 0 9 9
0 0 0 9
1 2
2 3
1 3
1 2

Sample Output

810
2140
693
810

Hints

對 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 是一選定值)

當妤嬌啟動太空船時,他沒想到的是這台太空船只能坐一人,於是他們......。

Problem Source

原TIOJ1789 / problem setter: fenzhang

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 500 65536
1 500 65536
2 500 65536
3 500 65536
4 500 65536
5 500 65536
6 500 65536
7 500 65536
8 500 65536
9 500 65536