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

hamayanhamayan's blog

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

包除原理

hamayanhamayan.hatenablog.jp

解説

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] + ...)で計算する。
計算量が心配だが、エラトステネスの篩を使えば大丈夫。