※ 引述《RockLee (Now of all times)》之铭言：
: ※ 引述《vocaloid (void *)》之铭言：
: : https://code.google.com/codejam
: : 参考答案好像还没公布
: : 请问第三题怎么作比较有效率呢?
: : large input 1 - 10 ^ 14
: : 2 - 10 ^ 100
: : 第一个我是跑测资前先建表 http://ideone.com/DDA2Sn
: : 第二个本来想offline建但不知会跑多久... 10^30就花了3分钟
: 假设我们定义 fair_root 为本身是回文且它的平方也是回文
: 我是先建到 15 位数的表观察它的规律性
: 发现从 N = 4 位数开始
: 有可能的 candidates 只有 N - 2 位数的 fair_root 在头尾第二位补 0 或 1
: 例如 N = 6 的 fair_root 为:
: 100001
: 101101
: 110011
: 111111
: 200002
: 则 N = 8 的 fair_root 的 candidates 为:
: 1 0 0000 0 1
: 1 0 0110 0 1
: 1 0 1001 0 1
: 1 0 1111 0 1
: 2 0 0000 0 2
: 1 1 0000 1 1
: 1 1 0110 1 1
: 1 1 1001 1 1
: 1 1 1111 1 1
: 2 1 0000 1 2
: 对这十个 candidates 实际验算可发现 N = 8 的 fair_root 共九个:
: 10000001
: 10011001
: 10100101
: 10111101
: 11000011
: 11011011
: 11100111
: 11111111
: 20000002
: 用这规律性去建表即使 online 建到 N = 50 的表也够快
嗯.. 你确定吗?
用 0,1,2 去造的好处是可以处理 进位 的状况
但, 考虑一下这个数字
522808225
这个是用 5 当个位数造出来的.
请问你的规律性找的到这个数字吗?
实际上, 就我所知, 这仍然是个 open problem.
这里有解释 necessay condition, 但是没有给出 sufficient.
http://arxiv.org/pdf/1210.7593v1.pdf
这个作者颇有名气, 不过这篇还没有 review 过
所以读的时候自己要注意.

522808225 本身是回文 但它的平方不是回文不符合我所称的 fair_root 的定义

my question is simple, based on you rulehow can I decide if the number I point out is or not?

根据我的rule 522808225显然不是 因为它不在我建的表中

then, how do you handle this case?

既然我已经先建好表了 我只需检查这个数在不在我的表中就知道它是不是 fair_root 了啊

不知道用0,1,2去建是否对所有N>0都成立呢

第一篇推文中的用0,1,2去建的方法对N>1都成立(N=1的fair_root是1,2,3)以题目要求而言3^25~=8*10^11而我所提的方法实际检查的candidates低于10^5故执行速度会更快 不过就这题而言并不一定需要这么快就是