創作內容

0 GP

ZeroJudge - d828 解題心得

作者:Not In My Back Yard│2018-07-25 20:49:48│巴幣:0│人氣:552
題目連結:d828

題目大意:給定N,求從第N列的巴斯卡三角形(如圖一)之第一項,往右上方加到沒得加為止(取10000的餘數)(如圖二)。(0 ≦ N ≦ 2 ^ 31 - 1)

(圖一)

(圖二)


思維:延展巴斯卡三角形,多觀察幾項後。發現題目所求第N項之棕色對角線和,是第N + 1項的費氏數列。以下的例子可以說明為何如此:

給定任何正整數M,求用若干的1、2之和為M的方法數(順序有差)。
例如,M=5,有1+1+1+1+1、1+1+1+2、1+1+2+1、
 1+2+1+1、2+1+1+1、1+2+2、
 2+1+2、2+2+1,共8種。
不難看出8=費氏數列第6項(等於前一項(M=4)之方式(最後為+1的方法數)+前二項(M=3)之方式(最後為+2的方法數))
而從組合數學的觀點來看,方法數可以由找空隙塞+2來取得,此例為8=C(5,0)+C(4,1)+C(3,2)。

所以第N項之棕色對角線和之值,為第N + 1項的費氏數列。


可是因為N可高達2147483647,不能採用預處理建表的方式。要快速計算的話,需要用到「快速冪」以及「矩陣」的性質。

快速冪:對於任意數字N都可表達為2的次方之和(也就是二進位),而由於次方的性質
        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。



費氏數列與「矩陣」:為迎合快速冪,我們需要找出費氏數列與矩陣的關係。由下圖,可建立出一些關係式。

M1,1 * F(N)+M1,2 * F(N+1)=F(N+1)
M2,1 * F(N)+M2,2 * F(N+1)=F(N+2)

可求出M1,1=0、M1,2=1、M2,1=1、M2,2=1。

再結合上方的快速冪,便可迅速地求出費氏數列的第N項。



此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大們可以提出來討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4070384
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|數論|快速冪|矩陣

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:初篇日誌 & Z... 後一篇:ZeroJudge - ...

追蹤私訊切換新版閱覽

作品資料夾

nnricn給寫作作家
https://t.me/nnr1cn 歡迎喜歡寫作的朋友或是對文學有興趣的人都可以加入電報群組哦!看更多我要大聲說昨天20:16


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】