作者bigload1234 (爺的霸氣你不懂)
看板Prob_Solve
標題[問題] NCPC的第H題
時間Thu Oct 11 01:28:10 2018
大家好，
最近參加競賽寫到一題看似簡單
其實有點難度的題目，但現在跟同學討論還是無解
題目大意：
輸入一正整數n,
將會產生一個累加的數m,
例如：n=12,
將會得到m=123456789101112,
最後求m除以2018的餘數為何？
困難點：
1.輸入的n的範圍是在2^64-1之內
2.題目限制時間1秒
如果單純的用累加字串是一定TLE，
因為輸入太大了，光加起來的時間就很長了，
因為輸入太大了，光加起來的時間就很長了，
目前跟同學討論應該是有一種規律，
但我們一直沒想出來，
不知版上有沒有人可以提供解法
感激不盡！
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.75.169.104
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1539192492.A.429.html
1F：推 LPH66: 一個很初階的提示: 長除法10/11 03:21
2F：→ LPH66: 注意這不是叫你直接寫長除法, 原因如你所說時間是不夠的10/11 03:21
3F：推 DJWS: 如果位數不變的話，每2018產生循環10/11 09:02
4F：→ DJWS: 如果位數改變的話，只好用暴力搜尋+預先計算 我猜是這樣10/11 09:03
5F：→ DJWS: 這題只有log10(2^64-1)=20位數 應該不必預先計算10/11 09:06
6F：推 ckc1ark: 用3*3的方陣來思考呢 多個[[10^n, 1, 0], [0, 1, 1], [0,10/11 10:13
7F：→ ckc1ark: 0, 1]] 乘 [1, 1, 1]這樣? n會變大10/11 10:13
8F：→ ckc1ark: 0, 1]] 乘 [1, 1, 1]這樣? n會變大10/11 10:13
9F：→ ckc1ark: 抱歉初始應該是[0,1,1]10/11 10:14
10F：→ pttworld: 這題光是12就有15位，最大千位萬位都有可能10/11 11:05
11F：→ pttworld: 10*1+90*2+900*3+9000*4+90000*5+900000*6+...10/11 11:08
12F：→ pttworld: 以上是位數長度10/11 11:08
13F：推 DJWS: 我說的位數是指0-9皆增加1位數、10-99皆增加2位數10/11 11:38
14F：→ DJWS: 每種位數分開處理 頂多就20種位數10/11 11:39
15F：→ DJWS: 1位數、2位數、3位數採用窮舉計算(horner's rule)10/11 11:41
16F：→ DJWS: 4位數以上，每2018個數字併成一組10/11 11:43
17F：→ pttworld: 每2018會循環的原理是什麼10/11 21:19
18F：推 rareone: Ummmm 就我所知這題有兩種寫法10/12 03:37
19F：→ rareone: 首先是中國剩餘定理的觀察 你可以把數字拆開來 2018 = 210/12 03:38
20F：→ rareone: * 100910/12 03:38
21F：→ rareone: 2 的模數很好處理 所以現在關心的是模100910/12 03:39
22F：→ rareone: 第一種做法：可以發現在同個位數下很有規律 用快速冪解決10/12 03:40
23F：→ rareone: 這題10/12 03:40
24F：→ rareone: 我自己在賽中的做法是 dp[目前模數][目前要加的數] 跑一10/12 03:42
25F：→ rareone: 次 rho 狀態最多1009*1009 種10/12 03:42
26F：→ rareone: 一旦發現回到之前的狀態10/12 03:44
27F：→ rareone: 把目前位數還剩下幾步模循環長度10/12 03:44
28F：→ rareone: 加到答案中10/12 03:44
29F：推 DJWS: 嚴謹來說是2018*2018會循環 原理就是樓上所述10/12 07:04
32F：→ ckc1ark: 好處是不用考慮modulus會有多大10/12 12:28
33F：推 ckc1ark: 阿 這就是rareone說的第一種做法吧?10/12 12:50
版上果然有人也參加了，實在沒想到這寫法，感謝各位相助！
※ 編輯: bigload1234 (114.39.29.138), 10/12/2018 14:34:13