$10^{12}$ くらい全列挙したくなったら、半分全列挙を検討すると良い？

$10^6$ くらいの大きさのグループを2つ作るのが半分全列挙。

問題例

• 4 つの整数 | アルゴ式 https://algo-method.com/tasks/861
• 半分全列挙による全探索の高速化 | アルゴリズムロジック
• ABC402 F - Path to Integer
• ABC271 F - XOR on Grid Path
• ABC427 F - Not Adjacent
• ABC032 D - ナップサック問題

メモ

• 計算量メタ(10^12だから半分全列挙)に頼らずに半分全列挙が使えそうとなる何かを見つけたい
• N=1 のときに半分全列挙をすると、片方が空列になるので注意が必要。N=1のときは半分全列挙せずに別途求めるのが無難そう。
• 制約によってDPだったり半分全列挙だったりする

https://youtu.be/EUZX4tBqo0M?si=S3ajpHoxDY2gmFkC

bit全探索よりBFSの方が早いことがある