問題リンク
No.2279 OR Insertion - yukicoder
解法
このような，ビット演算が絡む問題は「桁ごとに考える」ようにすると考えやすくなることが多いです．
「下から
桁目のビットが
になるような分割方法の数」という量を考えてみます．
そうすると，答えは となります．あとは，
に対して
を計算できればよさそうです．
ここで，分割した後の数の該当するビットを左から順に見ていくことを考えると，考えられる状態は「すでに が登場した」「まだ
が登場していない」の 2 種類に分けられることがわかります．さらに，一番最後まで見たときに，前者ならば該当するビットの論理和は
になり，後者ならば
となります．よって，「該当するビットがこれまでに登場したかいなか」で状態をまとめられそうです．このように考えると，
を DP で求める，という方針に行きつきやすいかもしれません．
では，実際に DP テーブルを組み立てて，下から 桁目のビットを求めることを考えてみましょう．
上記の考察をもとに，（左から
番目の切れ目で最後に分割を行い，
桁目のビットに
が登場したときの，分割方法の数）としてみます．
このときの遷移について考えてみましょう．このような，配列を分割する問題に対しての遷移は，直前に分割した箇所で場合分けするというのがかなり有効です．
まず，最後に分割してできるビット列のビット数が 以上の場合ですが，これはそのビット列
桁目が 0 か 1 かで場合分けをすればよいです．
ビット列の 桁目が 0 のときは，
の状態は変化しません．
一方， 桁目が 1 のときは，直前の
の状態によらず，次の
の状態は 1 になります．
よって，遷移は，
（
桁目が 0 のとき）
（
のように書けそうです．
問題は，最後に分割してできるビット列のビット数が より小さい場合ですが，このときはビット列
桁目は 0 とみなせます（leading zero がついたのだと考えれば，わかりやすいかもしれません）．よって，先ほどの場合の
桁目が 0 のときと同様にして，
のように書けます．
しかし，これの計算量は一回あたり であり，これを
回行うので，全体で
かかってしまいます．これでは間に合わないでしょう．そこで，この DP を累積和を用いて高速化します．
具体的には
という量を考えます．すると，先ほどの DP の遷移は，
を境界線として，それより大きい部分と小さい部分とのそれぞれで累積和を考えることにより，おおよそ
（
より大きい領域に対する DP の遷移）
（
（
などのように遷移できます（境界付近の値には注意が必要です）．
なお，このとき， の値は
に現れます（一番最後の切れ目まで切ったら該当ビットの論理和が 1 になっているような分割方法の数を考えているため）．
これにより，計算量は に落ちました．よって，この問題を解くことができました．
実装例
#861793 (C++17) No.2279 OR Insertion - yukicoder
感想
DP を使いそうだということは早い時点で気が付きましたが，遷移をどうするかでかなり悩まされ，遷移の方針が立った後も実装にかなり手間がかかりました．見た目以上に難しい問題だと思います．
