※ 引述《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