F - Limited Xor Subset CODE THANKS FESTIVAL 2017(Parallel)

問題概略
N個の正の整数が与えられる。
xorがKになるような選び方は何通りか

制約
N<=10^5
K<=10^5
sum(ai) <= 10^5

解法
O(NK)が間に合うなら、[i][k] := i番目までの中からkを作る通り　として
[i+1][k] += [i][k]
[i+1][k^A[i]] += [i][k]
と現状から遷移できるものを足していけば良い

今回
合計が10^5以下なので、数の種類は高々500
それらが何個あるかまとめておき同様に考える。
[i+1][k] += [i][k] * (偶数個の選び方 xorが0になるもの)
[i+1][k^A[i]] += [i][k] * (奇数個の選び方 xor がA[i]になるもの)
また、N個から偶数個、奇数個を選ぶ組み合わせはNの偶奇によらず同じである。

A[i]をソートして、kを今までのorまで見るようにもできる。
Aの合計は10^5だが、それぞれのiについてループは2 * A[i]程度しか行われないため

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        int K = ni();
        A = nia(N);
        P[] p = mato(A);
        int[][] dp = new int[p.length + 1][(int) 1e5 + 1];
        dp[0][0] = 1;
        for (int i = 0; i < p.length; i++) {
            for (int k = 0; k < 1e5 + 1; k++) {
                if (dp[i][k] <= 0) continue;
                //p[i].y個の中から偶数個選ぶ組み合わせ、奇数個選ぶ組み合わせ
                long zcom = mPow(2, p[i].y - 1);
                long kcom = mPow(2, p[i].y - 1);
                dp[i + 1][k] = (int) mSum(dp[i + 1][k], dp[i][k] * zcom);
                dp[i + 1][k ^ p[i].x] = (int) mSum(dp[i + 1][k ^ p[i].x], dp[i][k] * kcom);
            }
        }
        System.out.println(dp[p.length][K]);
    }