發表新討論
#10974: 解題心得


a5083 (assassin刺客大師)

學校 : 新北市立板橋高級中學
編號 : 28347
來源 : [140.116.138.99]
最後登入時間 ：
2017-06-27 17:13:56
d639. 企鵝村三兄弟penguin -- jack1 | From: [140.123.58.196] | 發表日期 : 2016-05-31 13:01

這題是不能用動態規劃建立矩陣來做，因為需要的空間太大了

所以我們只能用數學的方法找出規律性

首先我們發現

我們還可以觀察到

那麼要如何計算n呢

因為n很大所以不可能真的去乘n次

最好的方法是將n變成二進位來表示，在進行乘法

舉個例

不要忘記如果乘法中A^n的元素要mod(10007)

提示到這裡我想大家應該都知道解題步驟了

剩下就交給大家囉

 

 
ZeroJudge Forum