Sum is XOR [yukicoder 1189]

https://yukicoder.me/problems/no/1189

解説

https://yukicoder.me/submissions/538264

制約を順番に見ていこう。
まず、総和とXOR和が等しくなる条件というのは、数列BをすべてANDしたときに0になることが必要である。
これは総和で繰り上がりが発生してしまうとXOR和と差が出てしまうためである。
つまり、今回の問題は数列AからK個をビットがかぶらないように選べという問題となる。

怪しい制約

今回は制約にトリックがある。
A[i]が2¹⁰-1が上限となっているのに対し、個数がN個である。
ビットがかぶってはいけないので、大多数は数がかぶっていることになる。
よって、要素を選ぶときに数列Aの何番目かという風に取るのではなく、値がXである数列Aの要素を取るという風に考えると、
全探索がN通りから1023通りくらいになってだいぶ改善される。

次に、Kであるが、ビットが被らないように選ぶ必要があるが、制約より、ビットは10個しかないので、
10個も取ると全部ビットが埋まってしまう。
（鳩ノ巣原理）
なので、Kの上限は実際は10であり、それより大きい場合は解が存在しない。

bitDP

後はDPしよう。ビットを扱うので、bitDPと言ってもいい。
dp[use][msk] := use個の要素を選択済みで、全てのORを取るとmskになっているときの組み合わせ
遷移としては次に、どのような値を選択するかである。
このように選択すると、最終的な答えは、選択順が違うが結果が同じものも重複して数え上げられてしまう。
だが、重複の個数はK!通りなので、最後にこれで割ってやればいい。

int N, K, A[201010];
mint dp[11][1<<10];
Comb<mint, 201010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    
    map<int, int> cnt;
    rep(i, 0, N) cnt[A[i]]++;

    if (10 < K) {
        cout << 0 << endl;
        return;
    }

    dp[0][0] = 1;
    rep(use, 0, K) rep(msk, 0, 1 << 10) {
        rep(nxt, 0, 1 << 10) if(!(nxt & msk)) dp[use + 1][msk | nxt] += dp[use][msk] * cnt[nxt];
    }

    mint ans = 0;
    rep(msk, 0, 1 << 10) ans += dp[K][msk];
    ans *= com.ifac[K];
    cout << ans << endl;
}