ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - b955: 大怪獸 解題心得

Not In My Back Yard | 2018-09-28 22:03:03 | 巴幣 2 | 人氣 151

題目連結:


題目大意:
給定六個整數N、M、K、F0、F1、F2(絕對值皆不大於1, 000),代表有一函數F為以下定義:
F(0)=F0
F(1)=F1
F(2)=F2 且 
F(n)=N * F(n-1)+ M * F(n-2)+ K * F(n-3),當N > 2時。

接下來有一正整數X,代表接下來有X個值(皆 < 2 ^ 63,並 ≧ 0)。

求每個值代進上述F函數所得之結果,並將結果求除以1, 000, 007的餘數(而且必須為)。


解題思維:
看到那X個值會到2 ^ 63 - 1,就知道這不可能用暴力法硬A了吧XD

很明顯地,這必須用到與 d828 類似的矩陣,以及快速冪的概念。只是在這題並非2X2矩陣,而是3X3的版本(這邊很不負責地交給讀者推導,真的想不出來再參考本人的程式碼)。

接下來是矩陣的乘法,應該不需本人多說。

至於矩陣乘法為何那樣定義,可以參考 3Blue1Brown 的線性代數(Linear Algebra)系列,讀者們也許能從中看出一些端倪。

最後是取餘數。由於N、M、K、F0、F1、F2不一定為正,因此取餘數的結果有可能為負(如果是用內建的「%」運算的話,不是的話,就要看是怎麼寫的)。

而解決方案很簡單,先取完一次1, 000, 007餘數,判斷結果是否為負的。如果是,把結果加上1, 000, 007,就變成正的了;反之,可以不用加。至於為何經由如此操作仍然等價於原來的結果,請參見同餘

此外,小心矩陣相乘時的溢位。如果本身的矩陣的型態為「int」,則在相乘及相加要特別轉成「long long」型態,以免溢位。當然直接全部宣告成「long long」也是沒問題的。



此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作