Python で通す方法です．

Python では 3000 桁もある bit の popcount を高速に求める方法がなさそう（私は知りません…あったら教えてください）なので工夫が必要です．以下のサイトによれば，64bit 整数であれば \(O(1)\) で popcount を求めることができます．

明日使えないすごいビット演算

これを用いれば，\(N\) 桁の bit を，\(B\) 桁ごとに区切って \(N/B\) 個の bit として扱うことによって，計算量 \(O(N^3/B)\) を達成できます．

私のコンテスト中の実装です（\(B=60\) として実装しています）．実装例 (2154ms)

tester の Nyaan さんの実装も，同様の手法を取っているようです （\(B=63\)）．実装例 (1907ms)