作者babufong (哔哔)
看板puzzle
标题[中译] ProjectEuler 361 Subsequence of Thue-Morse sequence
时间Sun Dec 4 12:32:40 2011
361. Subsequence of Thue - Morse sequence
http://projecteuler.net/problem=361
Thue - Morse sequence {Tn} 是一个二进位制的数列，他符合以下条件：
T0 = 0
T2n = Tn
T2n+1 = 1 - Tn
我们可以知道 {Tn} 的前几项是这样的：
01101001
100101101001011001101001....
定义 {An} 是一个整数数列，而他的每一项用二进位制表示都有出现在 {Tn} 之中
举例来说，十进位制的 18 用二进位制表示就是 10010
10010 出现在 T8 到 T12 之间，所以 18 是 {An} 的其中一项
14 用二进位制表示为 1110，而 1110 从未出现在 {Tn} 中，故 14 不是 {An} 其中一项
An 的前几项我们也知道了，如下：
n 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
An 0 1 2 3 4 5 6 9 10 11 12 13 18 ...
我们还能证明出 A100 = 3251 而 A1000 = 80852364498
18
请计算出 Σ A10^k 的末九位
k=1
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 125.224.7.197
※ 编辑: babufong 来自: 125.224.7.197 (12/04 12:33)
1F：推 LPH66:啊, 一题平方数题号和幸运数题号出现了 12/04 16:51
2F：→ babufong:有助於解成就吗XD 12/05 01:22
3F：推 LPH66:是啊 我的幸运数成就才 42 题而已 12/05 06:41
4F：→ LPH66:(话说现在到 361 为止也才 66 个幸运数...) 12/05 06:42
5F：推 LPH66:唔, 我现在是找到一个演算法可以求 An 了 12/05 20:36
6F：→ LPH66:可是如果要求 A_{10^18} 我需要一个递归数列的前10^9项和.. 12/05 20:37
7F：→ LPH66:这鬼东西显然不可能先算好 偏偏OEIS上没有这个递归数列orz 12/05 20:38
8F：→ LPH66:看有没有人跟我核对一下: A_一万 的末九位是 843783988 12/05 20:41
9F：→ LPH66:然後 A_一万 这个数字是十进位34位 二进位113位 12/05 20:41
10F：→ babufong:我无法 我还是只会用excel解题orz 12/05 20:51
11F：推 LPH66:好像找到方法算了...结果还是用递归关系来做 12/06 00:26
12F：→ LPH66:不知道10^18时会不会很慢... 12/06 00:27
13F：推 utomaya:我也可以确定 A_一万 的末九位是 843783988 12/06 00:49
14F：→ utomaya:若没算错的话 A_1万=6717653396222467045074718843783988 12/06 00:50
15F：→ utomaya:加油了! 还剩4个席位... 12/06 00:51
16F：→ babufong:u大您不必紧张 前次改版已经将席位加到50席了XD 12/06 01:54
17F：推 LPH66:现在的进度是 A_{10^15} 要约25秒 然後索引多1位要3~4倍时间 12/06 01:58
18F：→ LPH66:在想要不要就乾脆半小时给他暴力跑出来好了... 12/06 01:58
19F：→ LPH66:结果因为记太多东西了 A_{10^16} 直接告诉我记忆体不足 XD 12/06 02:06
20F：→ LPH66:再来想想怎麽省... 12/06 02:06
21F：推 LPH66:最後还是回到跑比较快的 C 用了三分钟跑出了一个错的答案.. 12/08 20:20
22F：推 utomaya:如果没算错的话 A_{10^18}化作二进制应该有1126216794位数 12/09 00:59
23F：→ utomaya:好大的数字 12/09 01:00
24F：推 LPH66:看来果然哪里出事了...我算的 A_{10^18} 是二进位快15亿位 12/09 07:50
25F：推 LPH66:可恶, 原来是 long long overflow 了....orz 12/10 00:23
26F：→ LPH66:到 A_{10^17} 应该都是对的 但是 A_{10^18} 中间结果溢位了 12/10 00:25
27F：推 LPH66:终於搞定了! 拿到第 26 名 XD 12/10 03:12
28F：→ LPH66:(其实会一直钻这题就是想拿前百名的成就 XDDDD) 12/10 03:12