题解 AT_exawizards2019_e【Black or White】

标签：return int 题解 Black operator Modint White friend mod

设 \(P_b(k),P_w(k)\) 表示已经吃了 \(k\) 块巧克力，把所有黑/白巧克力都吃光了的概率。枚举最后一块黑/白巧克力被吃的时间，容易得到：

\[\begin{aligned} P_b(k)&=\sum_{i=1}^k\frac{\binom{i-1}{b-1}}{2^i}\\ P_w(k)&=\sum_{i=1}^k\frac{\binom{i-1}{w-1}}{2^i}\\ \end{aligned} \]

显然可以 \(O(b+w)\) 递推出来。设 \(P_a(k)=1-P_b(k)-P_w(k)\)，则第 \(k\) 个答案为 \(P_w(k-1)+\frac{P_a(k-1)}{2}\)。

// Problem: Black or White
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_exawizards2019_e
// Memory Limit: 1 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
    return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
    unsigned int x;
    Modint() = default;
    Modint(unsigned int x) : x(x) {}
    friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
    friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
    friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
    friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
    friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
    friend Modint operator/(Modint a, Modint b) {return a * ~b;}
    friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
    friend Modint operator~(Modint a) {return a ^ (mod - 2);}
    friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
    friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
    friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
    friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
    friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
    friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
    friend Modint& operator++(Modint& a) {return a += 1;}
    friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
    friend Modint& operator--(Modint& a) {return a -= 1;}
    friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
    friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
    friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

typedef Modint<1000000007> mint;
const int N = 2e5 + 5, mod = 1000000007;
const mint inv2 = (mod + 1) / 2;

int b, w;
mint fac[N], ifac[N];

inline mint C(int n, int m) {
    if(n < 0 || m < 0 || n < m) return 0;
    return fac[n] * ifac[m] * ifac[n - m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> b >> w;
    fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    rep(i, 2, b + w) {
        fac[i] = fac[i - 1] * i;
        ifac[i] = (mod - mod / i) * ifac[mod % i];
    }
    rep(i, 2, b + w) ifac[i] *= ifac[i - 1];
    mint Pb = 0, Pw = 0, now = 1;
    rep(i, 0, b + w - 1) {
        Pb += C(i - 1, b - 1) * now;
        Pw += C(i - 1, w - 1) * now;
        mint Pa = 1 - Pb - Pw;
        cout << Pw + Pa * inv2 << endl;
        now *= inv2;
    }
    return 0;
}

标签：return,int,题解,Black,operator,Modint,White,friend,mod
From： https://www.cnblogs.com/ruierqwq/p/18010321/AT_exawizards2019_e