>>381
最初の数が18以下だったので、bitDPで解いてみた。
皿が無いとき('_')の処理がかなりあやしい。

IDEONE早いな、1秒以下で答えが出た。
"123456789123456789"の例は, 2^18 * 98 = 2569万回+αほど回っている
最悪は 2^n * n^2 になるのかな
このやり方では、数字19桁くらいが数秒の限界

http://ideone.com/IRcyoU