作者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/cn.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