Pythonで実装する場合、実装方針によっては非自明な高速化が必要です。

たとえば、以下の手法で高速化できる可能性があります。

• 処理系をPython (PyPy 3.10-v7.3.12)にする
  • 解説執筆時点では、この処理系でのみACが出ています。
• bitDPを非再帰にする
  • これは、bit数が少ない要素から昇順に見ていくことで実現できます。
  • 追記:よく考えたら数の小さい順でよいですね…
• 整数型を交えず、すべて小数型で計算する
  • 型変換のオーバーヘッドは意外と馬鹿になりません。
• bitの部分集合を高速ゼータ変換で取得する
  • やや速くなります。しかし、これをしなければならないくらい遅いプログラムは解法を見直したり素直に速い言語に変える方が早いかもしれません。

実装例(PyPy3,1948ms)

(追記:未検証ですが、Nachiaさんのユーザー解説の方法も効果が大きいかもしれません。)