pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

包除原理

yukicoder 546: オンリー・ワン

https://yukicoder.me/problems/no/546 解法 高速メビウス変換というものを紹介する。高速メビウス変換というのは以下のような処理である。 for (int i = 0; i < n; i++) { for (int j = 0; j < 1 << n; j++) { if (~j >> i & 1) { a[j | 1 << i] -= a[j]; }…

AtCoder Grand Contest 005: D. ~K Perm Counting

http://agc005.contest.atcoder.jp/tasks/agc005_d