題目連結：
d828
題目大意：給定Ｎ，求從第Ｎ列的巴斯卡三角形（如圖一）之第一項，往右上方加到沒得加為止（取１００００的餘數）（如圖二）。（０ ≦ Ｎ ≦ ２ ^ ３１ - １）
![]()
（圖一）
![]()
（圖二）
思維：延展巴斯卡三角形，多觀察幾項後。發現題目所求第Ｎ項之棕色對角線和，是第Ｎ ＋ １項的費氏數列。以下的例子可以說明為何如此：
給定任何正整數Ｍ，求用若干的１、２之和為Ｍ的方法數（順序有差）。
例如，Ｍ＝5，有１＋１＋１＋１＋１、１＋１＋１＋２、１＋１＋２＋１、
１＋２＋１＋１、２＋１＋１＋１、１＋２＋２、
２＋１＋２、２＋２＋１，共８種。
不難看出８＝費氏數列第６項（等於前一項（Ｍ＝４）之方式（最後為＋１的方法數）＋前二項（Ｍ＝３）之方式（最後為＋２的方法數））
而從組合數學的觀點來看，方法數可以由找空隙塞＋２來取得，此例為８＝Ｃ（５,０）＋Ｃ（４,１）＋Ｃ（３,２）。
所以第Ｎ項之棕色對角線和之值，為第Ｎ ＋ １項的費氏數列。
可是因為Ｎ可高達２１４７４８３６４７，不能採用預處理建表的方式。要快速計算的話，需要用到「快速冪」以及「矩陣」的性質。
快速冪：對於任意數字Ｎ都可表達為２的次方之和（也就是二進位），而由於次方的性質
N ^ A 乘以 N ^ B＝N ^ （A + B）。
所以可以先做出某數的 1 次方、 2 次方、 4 次方、 8 次方等等，便可快速求出某數的任意次方。
例如 5 ^ 13 ，我們先計算 5 ^ 1 、 5 ^ 2 、 5 ^ 4……（每一項都是上一項自乘自己一次）。而因為 13 的二進位為 1101，所以代表著 5 ^ 13 = 5 ^ 8 × 5 ^ 4 × 5 ^ 1。
費氏數列與「矩陣」：為迎合快速冪，我們需要找出費氏數列與矩陣的關係。由下圖，可建立出一些關係式。
Ｍ１,１ * Ｆ（Ｎ）＋Ｍ１,２ * Ｆ（Ｎ＋１）＝Ｆ（Ｎ＋１）
Ｍ２,１ * Ｆ（Ｎ）＋Ｍ２,２ * Ｆ（Ｎ＋１）＝Ｆ（Ｎ＋２）
可求出Ｍ１,１＝０、Ｍ１,２＝１、Ｍ２,１＝１、Ｍ２,２＝１。
再結合上方的快速冪，便可迅速地求出費氏數列的第Ｎ項。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大們可以提出來討論。
創作內容
ZeroJudge - d828 解題心得
ZeroJudge (0)
（圖一）
（圖二）
