写一下我解这题的心路历程好了 XD 引文後有雷 ※ 引述《babufong (哔哔)》之铭言： : 361. Subsequence of Thue - Morse sequence : http://projecteuler.net/problem=361 : Thue - Morse sequence {Tn} 是一个二进位制的数列，他符合以下条件： : T0 = 0 : T2n = Tn : T2n+1 = 1 - Tn : 我们可以知道 {Tn} 的前几项是这样的： : 01101001100101101001011001101001.... : 定义 {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 一开始我是用了另一个等价的 T_n 的定义在做: 从"0"开始 把目前有的字串 0 1 反转之後接到後面 无限接下去就是 T_n 於是在想到底什麽型式是不会出现的 很容易找到了 111 000 11011 00100 但发现 1101011 0010100 这种也要时我果断放弃 後来回到原来的定义才发现原来直接用"延伸"的方式去找就好 例如 10010 这一串 表示前面必然有个地方有 10010 => 100 这个字串在 用类似的道理就可以知道 所有够长的字串都能够由某个较短的字串做以下四个动作之一得到: (1) 做 1 -> 10, 0 -> 01 (2) 做 1 -> 10, 0 -> 01 但去尾 (3) 做 1 -> 01, 0 -> 10 但截头 (4) 做 1 -> 01, 0 -> 10 但截头去尾 例如 100 做 (1) 得到 100101 做 (2) 得到 10010 做 (3) 得到 11010 做 (4) 得到 1101 仔细比较得到的这四个数 会发现永远有 (4) < (2) < (3) < (1) < 长一点字串的 (4) 因此 我们会得到结论 长度 4 的字串前半段是长度 2 做 (1) 後半段是长度 3 做 (4) 长度 5 的字串前半段是长度 3 做 (2) 後半段是长度 3 做 (3) 长度 6 的字串前半段是长度 3 做 (1) 後半段是长度 4 做 (4) 依此类推 这样一来 长度 n 的字串的个数 S(n) 就是如下的数列 1 2 3 5 6 8 10 11 12 14 16 18 20 21 22 23 24 ... (这就是我在前篇推文提到的数列) 它的递回关系是 S(2n) = S(n)+S(n+1) n≧2 S(2n+1) = 2S(n+1) n≧2 S(1) = 1, S(2) = 2, S(3) = 3 那麽根据上面得到的这个规则 A_n 就只要去求 S(n) 的前几项和到正好超过 再去计算它是那个长度的哪个位置 是前半还是後半 是由长度多少字串的第几个延伸来的 就可以知道它是什麽字串 结果 A_{10^15} 因为用 Mathematica 直接生字串生到记忆体炸掉了...XD 这中间为了节省时间我做了非常多数学计算 甚至把上面这数列的前 N 项和写了一个公式出来 (由於这数列等於 1.5n-1.5 加上一个很有规律升降的数列 前 N 项和可以由 Σ(1.5n-1.5) 再去调整 这样就有公式了) 但无论如何总是快不起来 就算记忆体不炸掉要算出 A_{10^18} 也要半小时 回头看到题目发现范例特别把 18 (10010) 出现在 T_8 ~ T_12 给说出来 这才打醒我不必要去记整个字串 去记它在字串的哪里就好了... 而根据给定的 T_n 的定义 这个延伸的动作就变得像是乘以 2 一样简单 不过要从在哪里的字串去求出那一位是什麽也让我想了一会儿 然後我才想起一件很重要的事: T_n 其实还有另一个等价定义 T_n = {1, 若 n 的二进位表示法中 1 的个数为奇数 {0, 若 n 的二进位表示法中 1 的个数为偶数 也就是俗称(?)的 Parity 利用这一点 给定范围之後我能够一位一位算过去求余数 发现这一点之後我改用 C 写 求 Parity 的部份我特别写了一支小小的组合语言副程式嵌进去 利用了组合语言里会根据结果的 Parity 设定旗标的功能直接读出我要的 Parity (这个副程式组译之後只有 20 byte 算是满自豪的 XD 所以就直接写成字串後当成函式来呼叫了) 不过跑出来的结果还是不对 (这个时候 A_{10^18} 只要约一分钟就能有结果) 一直到 utomaya 的推文 (A_{10^18} 约是 11 亿位二进位) 之後我回头检查算式 才发现原来是计算上面那数列的前 N 项和的公式的中间结果溢位了... 把这个溢位改掉之後才终於得到正确答案 orz 总计从我开始解这题的星期日开始 边忙要交的作业边解 然後还跨过了这周四某科的期中考 一直到现在下一题快出来了才把这题干掉...orz -- 来去把 360 也干掉拿最新五题的成就 @_@ -- LPH [acronym] = Let Program Heal us -- New Uncyclopedian Dictionary, Minmei Publishing Co. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.28.91