推 LPH66: 一個很初階的提示: 長除法10/11 03:21
→ LPH66: 注意這不是叫你直接寫長除法, 原因如你所說時間是不夠的10/11 03:21
推 DJWS: 如果位數不變的話,每2018產生循環10/11 09:02
→ DJWS: 如果位數改變的話,只好用暴力搜尋+預先計算 我猜是這樣10/11 09:03
→ DJWS: 這題只有log10(2^64-1)=20位數 應該不必預先計算10/11 09:06
推 ckc1ark: 用3*3的方陣來思考呢 多個[[10^n, 1, 0], [0, 1, 1], [0,10/11 10:13
→ ckc1ark: 0, 1]] 乘 [1, 1, 1]這樣? n會變大10/11 10:13
→ ckc1ark: 0, 1]] 乘 [1, 1, 1]這樣? n會變大10/11 10:13
→ ckc1ark: 抱歉初始應該是[0,1,1]10/11 10:14
→ pttworld: 這題光是12就有15位,最大千位萬位都有可能10/11 11:05
→ pttworld: 10*1+90*2+900*3+9000*4+90000*5+900000*6+...10/11 11:08
→ pttworld: 以上是位數長度10/11 11:08
推 DJWS: 我說的位數是指0-9皆增加1位數、10-99皆增加2位數10/11 11:38
→ DJWS: 每種位數分開處理 頂多就20種位數10/11 11:39
→ DJWS: 1位數、2位數、3位數採用窮舉計算(horner's rule)10/11 11:41
→ DJWS: 4位數以上,每2018個數字併成一組10/11 11:43
→ pttworld: 每2018會循環的原理是什麼10/11 21:19
推 rareone: Ummmm 就我所知這題有兩種寫法10/12 03:37
→ rareone: 首先是中國剩餘定理的觀察 你可以把數字拆開來 2018 = 210/12 03:38
→ rareone: * 100910/12 03:38
→ rareone: 2 的模數很好處理 所以現在關心的是模100910/12 03:39
→ rareone: 第一種做法:可以發現在同個位數下很有規律 用快速冪解決10/12 03:40
→ rareone: 這題10/12 03:40
→ rareone: 我自己在賽中的做法是 dp[目前模數][目前要加的數] 跑一10/12 03:42
→ rareone: 次 rho 狀態最多1009*1009 種10/12 03:42
→ rareone: 一旦發現回到之前的狀態10/12 03:44
→ rareone: 把目前位數還剩下幾步模循環長度10/12 03:44
→ rareone: 加到答案中10/12 03:44
推 DJWS: 嚴謹來說是2018*2018會循環 原理就是樓上所述10/12 07:04
→ ckc1ark: 好處是不用考慮modulus會有多大10/12 12:28
推 ckc1ark: 阿 這就是rareone說的第一種做法吧?10/12 12:50
版上果然有人也參加了,實在沒想到這寫法,感謝各位相助!
※ 編輯: bigload1234 (114.39.29.138), 10/12/2018 14:34:13