AOJ 2446 Enumeration

概要

包除原理と期待値の線形性（誤用かも）で解きました

既存の解説はメビウス変換が多かったので自分の解法を書いておきます。

問題

N個の整数S1...Snが与えられ、それらの整数をランダムにいくつか選ぶ。ここで(1<=i<=n)なるiで各Siが選ばれる確率はPi/100である。また、選ばれた整数集合をT1...Tkと呼ぶことにする。この時1以上M以下の整数について、T1...Tkの少なくとも一つで割り切ることができるようなものの個数の期待値を求めよ。

制約

1<= n <= 20

1<=m, ai <= 10^18

1<=pi<=99

解説

まず、Tについて1以上M以下の整数でT1...Tkの少なくとも一つで割り切れる個数というのは集合Tを決め打った場合、包除原理でO(N * 2^N)で解けます

↓この記事が詳しいです

https://compro.tsutaj.com//archive/181015_incexc.pdf

全てのTについて上の方法で求めようとすると間に合わないので式変形を考えます。

ここで、P(T)を集合としてTが選ばれる確率

V(T)を1~Mの内Tの少なくとも一つで割り切れる個数とすると

下の一つ目の式のように答えを表せますが

P2(U)をランダムなTについて、U⊆Tとなる確率とすると

1つ目の式は二つ目の式に変形できます。

何をしてるかというと、たとえばS={2, 3, 5}だとして

U={2, 3}の時の包除の計算は、T={2, 3},  {2, 3, 5}の時に行われますが

T(T⊆S)ごとにU(U⊆T)について計算するのではなく

U(U⊆S)毎にまとめて全てを計算するといった感じです(説明が雑になりすみません)

↓参考(Sが{2, 3}の場合)

using bint =__int128;
__int128 toi128(string &s) {
    __int128 ret = 0;
    for (int i = 0; i < s.length(); i++)
        if ('0' <= s[i] && s[i] <= '9')
            ret = 10 * ret + s[i] - '0';
    return ret;
}

std::istream &operator>>(std::istream &iss, __int128& v){
    string S;
    iss>>S;
    v = toi128(S);
    return iss;
}
bint gcd2(bint a, bint b) {
    while (b) a %= b, swap(a, b);    return a;
}

void solve() {
    bint N, M;
    cin >> N >> M;
    dna(A, N);
    dna(P_, N);
    vector<double> P(N);
    rep(i, N) {
        P[i] = P_[i] / (double)100;
    }
    double res=0;
    rep(mas, 1, 1<<N){
        bint mul = 1;
        double per=1;
        rep(i, N){
            //masのibit目を取得
            if(bget(mas, i)){
                bint g = gcd2(mul, A[i]);
                mul *= A[i];
                mul /= g;
                per *= P[i];
                if(mul > M)goto end;
            }
        }
        if(bcou(mas)%2){
            res += (int)(M/mul) * per;
        }else{
            res -= (int)(M/mul) * per;
        }
        end:;
    }
    cout << res << endl;
}