※ 引述《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 的表也够快