はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける包除原理問題まとめ

競技プログラミング

包除原理

　

  • 数え上げをする時の定理 ここが詳しい ここの包除原理の欄も詳しい
  • 基本は状態系包除原理
  • 状態系包除原理を個数に注目して個数系包除原理にするテクがある（抽象化による状態圧縮）
    • 例
    • n(AorBorC) = n(A) + n(B) + n(C) - n(A&B) - n(B&C) - n(C&A) + n(A&B&C)
    • もし、「dp[i] := i個の&で表現できる組み合わせ数」が高速に計算できれば、
    • n(AorBorC) = dp[1] - dp[2] + dp[3]
    • 事前計算が高速にできれば包除原理計算部分をO(2^N)からO(N)に削減できる
    • 問題によっては「dp[i] := &でつながれている個数の偶奇がiであるときの組み合わせ数」のように更に状態を圧縮出来る場合もある これ
  • 順列の組み合わせ数は、組合せの組み合わせ数と包除原理から求めるテクがある 問題1 問題2
  • 約数系包除原理というのもある（まだ完全に理解できてないかも）
    • drkenさんの記事のまとめ DEGwerさんの数え上げテクニック集 に記述がある
    • 上の包除原理とは少し異なる
    • DEGwerさんの資料抜粋
      • あるパラメタがkの倍数である場合
        • dp[k]を確定する時に重複して数えているkの倍数を引く
        • dp[k] = （kに対する何らかの計算）- Σ{lはkの倍数}dp[l]
        • 計算量はエラトステネスの篩と同じ形になるのでO(NlogN)
        • 計算はkを大きい順からやっていく。k以上から倍数の数を引いていくことで丁度kを求める感じ
      • あるパラメタがkの約数である
        • dp[k]を確定する時に重複して数えているkの約数を引く
        • dp[k] = （kに対する何らかの計算）- Σ{lはkの約数}dp[l]
        • 計算量はO(Nf(N))、f(x)はxの約数の個数（約数の個数は10^9で10^3くらい）
        • 計算はkを小さい順からやっていく。これも、k以下から約数の数を引いていくことで丁度kを求める感じ
    • 包除原理に見られる(-1)^kは出てこない
  • 状態系包除原理においてメビウス関数を使って(-1)^k部分を決定するテクがある
    • n(2) + n(3) + n(5) - n(6) - n(10) - n(15) + n(30)みたいな計算の+,-,0を決定できる
    • 具体的には
      • 0 : 平方数が因数に含まれる（包除原理での計算外としてみなせる）
      • -1 : 素因数の個数が奇数
      • 1 : 素因数の個数が偶数
    • メビウス関数ってO(NlogN)以外の高速な計算法ある？

問題

工事中

http://kmjp.hatenablog.jp/search?q=包除原理
http://kimiyuki.net/categories/inclusion-exclusion-principle/
http://pekempey.hatenablog.com/search?q=包除原理


以下、解説



















解説

yukicoder No.316 もっと刺激的なFizzBuzzをください

lcm辺りの処理が必要だが、包除原理を適用するだけ

ABC003 D. AtCoder社の冬

http://abc003.contest.atcoder.jp/submissions/1227903
4要素の包除原理の勉強。公式解説の図も分かりやすいし、以下のサイトも分かりやすい。(特にコードが)
公式解説 : https://www.slideshare.net/chokudai/abc003
http://tkori.hateblo.jp/entry/2015/12/16/180521

yukicoder No.391 CODING WAR

hamayanhamayan.hatenablog.jp

SRM602 Div2 Hard BlackBoxDiv2

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)


int mod = 1000000007;
int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
template<class... T> int add(int x, T... y) { return add(x, add(y...)); }
int mul(int x, int y) { return 1LL * x * y % mod; }
template<class... T> int mul(int x, T... y) { return mul(x, mul(y...)); }
int sub(int x, int y) { return add(x, mod - y); }
int modpow(int a, long long b) { int ret = 1; while (b > 0) { if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod; b >>= 1; } return ret; }
int modinv(int a) { return modpow(a, mod - 2); }
int fac[201010], ifac[201010];
void initfac() {
    fac[0] = ifac[0] = 1;
    rep(i, 1, 201010) fac[i] = 1LL * i * fac[i - 1] % mod;
    rep(i, 1, 201010) ifac[i] = modinv(fac[i]);
}
int aCb(int a, int b) {
    if (b < 0 || a < b) return 0;
    return (1LL * fac[a] * ifac[a - b] % mod) * ifac[b] % mod;
}
//-----------------------------------------------------------------------------------
struct BlackBoxDiv2 {
    int W, H;
    int cnt(int x, int y) {
        return mul(aCb(W, x), aCb(H, y), modpow(2, x*y));
    }
    int count(string front, string side) {
        initfac();

        W = 0, H = 0;
        for (char c : front) if (c == 'B') W++;
        for (char c : side) if (c == 'B') H++;

        int ans = 0;
        rep(x, 0, W + 1) rep(y, 0, H + 1) {
            int com = cnt(x, y);

            int p = (W + H) - (x + y);
            if (p % 2 == 0) ans = add(ans, com);
            else ans = sub(ans, com);
        }
        return ans;
    }
};

cnt(x,y) := W*Hのマス目からx列分,y行分選んでブロックを入れる組合せ
とすると cnt(x,y) = aCb(W,x) * aCb(H,y) * 2^(xy) である。
あとは包除原理をつかって計算していく。
例えば3*3のマスにブロックを入れるならば、
cnt(3,3)
- cnt(2,3) - cnt(3,2)
+ cnt(1,3) + cnt(2,2) + cnt(3,1)
- cnt(0,3) - cnt(1,2) - cnt(2,1) - cnt(3,0)
+ cnt(0,2) + cnt(1,1) + cnt(2,0)
- cnt(0,1) - cnt(1,0)
+ cnt(0,0)
って感じ

Codeforces Round #251 Div2 E. Devu and Birthday Celebration

http://codeforces.com/contest/439/submission/26469848
包除原理の式の理解ができてない。公式解説にもkmjpさんの解説にもあるけど、どんだけ考えても分からんのだけど。
http://kmjp.hatenablog.jp/entry/2014/06/05/1000
http://codeforces.com/blog/entry/12545
メビウスの反転公式による高速化もできるらしい。

  • Educational Codeforces Round 20 F. Coprime Subsequences

http://codeforces.com/contest/803/submission/26796820
dp[i] := 部分列の中でgcdがiとなる組合せ
例えば、部分列の中で6の倍数の個数が3個あった場合、この数を使った部分列の数は2^3-1通りある。
しかし、これは12の倍数や18の倍数などを含んでしまっている。
そのため、包除原理を使って、dp[6] = 2^3-1 - (dp[12] + dp[18] + ...)で計算する。
計算量が心配だが、エラトステネスの篩を使えば大丈夫。