O(3^N) のビット DP Java編（paizaランク S 相当）

説明

step1 では、動的計画法の遷移は以下のようになっており、時間計算量は O(2^N × 2^N) = O(4^N) 時間でした。

for s = 0 to 2^N - 1:
    for t = 0 to 2^N - 1:
        if t が s の部分集合なら:
            dp[s] = max(dp[s], dp[(s と t の差集合)] + Z[t])

実は、もっと効率的に実装することができます。
この遷移は、集合 s の部分集合 t を用いて遷移しています。
集合 s = {1,3} = 101 の部分集合 t = 101, 100, 001, 000 です。
ここで、以下の 2 点がわかります。
・集合 s で 1 の桁は、部分集合 t で 0 か 1
・集合 s で 0 の桁は、部分集合 t で必ず 0
つまり、集合 s の部分集合を列挙するには、s の 1 の部分の 0, 1 の組合せを全通り列挙すればよいです。
この考えに基づき、以下の方法を実装することで、効率的に部分集合を列挙できます。

t = s
while t >= 0:
    t &= s  # s と t の論理積をとる
    # 部分集合 t に対する処理
    t -= 1

これを用いてより高速な方法で問題を解いてみましょう。

問題

この問題は前回の問題と N の制約のみが異なります。

paiza 大学院には N 人の学生がいます。
人 i には整数 A_i が割り当てられています。
いまから N 人を 1 つ以上のいくつかのグループにわけます。
グループ j に属している人の集合を S_j = {i_1, i_2, ... , i_{c_j}} とします。ここで、c_j はグループ j の人数を表します。
このとき、グループ j の相性は Z_{S_j} := (A_{i_1} XOR A_{i_2} XOR ... XOR A_{i_{c_j}}) × c_j として定義されます。
どの人も必ず 1 つのグループに属さなければなりません。
すべての人のグループ分けが終わった後、各グループの相性の総和 Σ Z_{S_j} の最大値を求めてください。