https://yukicoder.me/problems/no/1189
解説
https://yukicoder.me/submissions/538264
制約を順番に見ていこう。
まず、総和とXOR和が等しくなる条件というのは、数列BをすべてANDしたときに0になることが必要である。
これは総和で繰り上がりが発生してしまうとXOR和と差が出てしまうためである。
つまり、今回の問題は数列AからK個をビットがかぶらないように選べという問題となる。
怪しい制約
今回は制約にトリックがある。
A[i]が210-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; }