(略解です。正式な解説は後日公開されます。)

面白くないビットすごろく の \(\mathrm{O}(\log^3 N)\) 時間解法と似たようなことをすると解ける。