PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] NCPC的第H題

看板Prob_Solve (計算數學 Problem Solving)作者 (爺的霸氣你不懂)時間6年前 (2018/10/11 01:28), 6年前編輯推噓9(9推 0噓 24→)
留言33則, 5人參與, 6年前最新討論串1/1
大家好， 最近參加競賽寫到一題看似簡單 其實有點難度的題目，但現在跟同學討論還是無解 題目大意： 輸入一正整數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://www.ptt.cc/bbs/Prob_Solve/M.1539192492.A.429.html
推
10/11 03:21, 6年前 , 1F
一個很初階的提示: 長除法
10/11 03:21, 1F
→
10/11 03:21, 6年前 , 2F
注意這不是叫你直接寫長除法, 原因如你所說時間是不夠的
10/11 03:21, 2F
推
10/11 09:02, 6年前 , 3F
如果位數不變的話，每2018產生循環
10/11 09:02, 3F
→
10/11 09:03, 6年前 , 4F
如果位數改變的話，只好用暴力搜尋+預先計算 我猜是這樣
10/11 09:03, 4F
→
10/11 09:06, 6年前 , 5F
這題只有log10(2^64-1)=20位數 應該不必預先計算
10/11 09:06, 5F
推
10/11 10:13, 6年前 , 6F
用3*3的方陣來思考呢 多個[[10^n, 1, 0], [0, 1, 1], [0,
10/11 10:13, 6F
→
10/11 10:13, 6年前 , 7F
0, 1]] 乘 [1, 1, 1]這樣? n會變大
10/11 10:13, 7F
→
10/11 10:13, 6年前 , 8F
0, 1]] 乘 [1, 1, 1]這樣? n會變大
10/11 10:13, 8F
→
10/11 10:14, 6年前 , 9F
抱歉初始應該是[0,1,1]
10/11 10:14, 9F
→
10/11 11:05, 6年前 , 10F
這題光是12就有15位，最大千位萬位都有可能
10/11 11:05, 10F
→
10/11 11:08, 6年前 , 11F
10*1+90*2+900*3+9000*4+90000*5+900000*6+...
10/11 11:08, 11F
→
10/11 11:08, 6年前 , 12F
以上是位數長度
10/11 11:08, 12F
推
10/11 11:38, 6年前 , 13F
我說的位數是指0-9皆增加1位數、10-99皆增加2位數
10/11 11:38, 13F
→
10/11 11:39, 6年前 , 14F
每種位數分開處理 頂多就20種位數
10/11 11:39, 14F
→
10/11 11:41, 6年前 , 15F
1位數、2位數、3位數採用窮舉計算(horner's rule)
10/11 11:41, 15F
→
10/11 11:43, 6年前 , 16F
4位數以上，每2018個數字併成一組
10/11 11:43, 16F
→
10/11 21:19, 6年前 , 17F
每2018會循環的原理是什麼
10/11 21:19, 17F
推
10/12 03:37, 6年前 , 18F
Ummmm 就我所知這題有兩種寫法
10/12 03:37, 18F
→
10/12 03:38, 6年前 , 19F
首先是中國剩餘定理的觀察 你可以把數字拆開來 2018 = 2
10/12 03:38, 19F
→
10/12 03:38, 6年前 , 20F
* 1009
10/12 03:38, 20F
→
10/12 03:39, 6年前 , 21F
2 的模數很好處理 所以現在關心的是模1009
10/12 03:39, 21F
→
10/12 03:40, 6年前 , 22F
第一種做法：可以發現在同個位數下很有規律 用快速冪解決
10/12 03:40, 22F
→
10/12 03:40, 6年前 , 23F
這題
10/12 03:40, 23F
→
10/12 03:42, 6年前 , 24F
我自己在賽中的做法是 dp[目前模數][目前要加的數] 跑一
10/12 03:42, 24F
→
10/12 03:42, 6年前 , 25F
次 rho 狀態最多1009*1009 種
10/12 03:42, 25F
→
10/12 03:44, 6年前 , 26F
一旦發現回到之前的狀態
10/12 03:44, 26F
→
10/12 03:44, 6年前 , 27F
把目前位數還剩下幾步模循環長度
10/12 03:44, 27F
→
10/12 03:44, 6年前 , 28F
加到答案中
10/12 03:44, 28F
推
10/12 07:04, 6年前 , 29F
嚴謹來說是2018*2018會循環 原理就是樓上所述
10/12 07:04, 29F
推
10/12 12:28, 6年前 , 30F
我的constant space解 https://tinyurl.com/ya9dx59d
10/12 12:28, 30F
推
10/12 12:28, 6年前 , 31F
我的constant space解 https://tinyurl.com/ya9dx59d
10/12 12:28, 31F
→
10/12 12:28, 6年前 , 32F
好處是不用考慮modulus會有多大
10/12 12:28, 32F
推
10/12 12:50, 6年前 , 33F
阿 這就是rareone說的第一種做法吧?
10/12 12:50, 33F
版上果然有人也參加了，實在沒想到這寫法，感謝各位相助！ ※ 編輯: bigload1234 (114.39.29.138), 10/12/2018 14:34:13
‣ 更多 bigload1234 的文章
文章代碼(AID): #1RlZQiGf (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 bigload1234 的文章
文章代碼(AID): #1RlZQiGf (Prob_Solve)