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

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