Problem:


Score : 700 points

Problem Statement

Today, Snuke will eat B pieces of black chocolate and W pieces of white chocolate for an afternoon snack.

He will repeat the following procedure until there is no piece left:

Choose black or white with equal probability, and eat a piece of that color if it exists.

For each integer i from 1 to B+W (inclusive), find the probability that the color of the i-th piece to be eaten is black.
It can be shown that these probabilities are rational, and we ask you to print them modulo 10^9 + 7, as described in Notes.

Notes

When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers and x is not divisible by 10^9 + 7
(under the constraints of the problem, such representation is always possible).
Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.

Constraints

All values in input are integers.

1 \leq B,W \leq 10^{5}

Input

Input is given from Standard Input in the following format:

B W

Output

Print the answers in B+W lines. In the i-th line, print the probability that the color of the i-th piece to be eaten is black, modulo 10^{9}+7.

Sample Input 1

2 1

Sample Output 1

500000004
750000006
750000006

There are three possible orders in which Snuke eats the pieces:

white, black, black

black, white, black

black, black, white

with probabilities \frac{1}{2}, \frac{1}{4}, \frac{1}{4}, respectively. Thus, the probabilities of eating a black piece first, second and third are \frac{1}{2},\frac{3}{4} and \frac{3}{4}, respectively.

Sample Input 2

3 2

Sample Output 2

500000004
500000004
625000005
187500002
187500002

They are \frac{1}{2},\frac{1}{2},\frac{5}{8},\frac{11}{16} and \frac{11}{16}, respectively.

Sample Input 3

6 9

Sample Output 3

500000004
500000004
500000004
500000004
500000004
500000004
929687507
218750002
224609377
303710940
633300786
694091802
172485353
411682132
411682132



Sample input:
2 1


Sample output:
500000004
750000006
750000006

Submission status: Accepted

Solution code:
#a,b,c = [int(i) for i in input().split()]

import sys
input = sys.stdin.readline

SIZE=200002; 
MOD = 10**9+7
bai= 500000000+4

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0



b,w = [int(i) for i in input().split()]

c = min(b,w)
for i in [0]*c:
    print(bai)

ans = bai
p=pow(bai,c+1,MOD)
for i in range(c,b+w):
#    print(p,i-1,i-w,b-1)
    ans += p*(choose(i-1,i-w) - choose(i-1,b-1))
    p= p*bai; p%=MOD
    ans = ans%MOD
    print(ans)

Submission status: Accepted

Solution code:
INF = 1000000007

def ex_gcd(a, b):
	x1, x2 = 0, 1
	y1, y2 = 1, 0
	q = 0
	while b:
		x1, x2 = x2, x1 - q * x2
		y1, y2 = y2, y1 - q * y2
		q = a // b
		a, b = b, a % b
	return a, x2, y2

def invert(x, mod=INF):
	return ex_gcd(x, mod)[1] % mod

B, W = map(int, input().split())

p = 0
q = 0
c1, c2 = 0, 1
d1, d2 = 0, 1
s = 1
for k in range(1, B + W + 1):
	if B + 1 < k:
		c1 = c2
		c2 *= invert((k - 1) - B) * (k - 1) % INF
		c2 %= INF
	if W + 1 < k:
		d1 = d2
		d2 *= invert((k - 1) - W) * (k - 1) % INF
		d2 %= INF
	if B < k:
		p += (c2 - c1) * s % INF
		p %= INF
	if W < k:
		q += (d2 - d1) * s % INF
		q %= INF
	print((q + invert(2) * (1 - p - q)) % INF)
	s *= invert(2)
	s %= INF

Submission status: Accepted

Solution code:
Q = 10**9+7
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

B, W = map( int, input().split())
Z = getInv(B+W)
I = [1]*(B+W+1)
for i in range(1,B+W+1):
    I[i] = (I[i-1]*Z[i])%Q

F = [1]*(B+W+1)
for i in range(1,B+W+1):
    F[i] = F[i-1]*i%Q
w = 0
b = 0
for i in range(1,B+W+1):
    if i - 1 < B and i - 1 < W:
        print(I[2])
    elif i - 1 == W and i - 1< B:
        w = pow(I[2],i-1,Q)
        print(((1 -  w)%Q*I[2]%Q + w)%Q)
    elif i - 1 >= W and i - 1< B: #i > B
        w += F[i-2]*I[i-1-W]%Q*I[W-1]%Q*pow(I[2],i-1,Q)%Q
        w %= Q
        print(((1 -  w)%Q*I[2]%Q + w)%Q)
    elif i - 1 == B and i - 1 < W:
        b = pow(I[2],i-1,Q)
        print((1-b)%Q*I[2]%Q)
    elif i - 1 >= B and i - 1 < W: #i > W
        b += F[i-2]*I[i-1-B]%Q*I[B-1]%Q*pow(I[2],i-1,Q)%Q
        b %= Q
        print((1-b)%Q*I[2]%Q)
    elif i - 1 == B and i - 1 == W:
        w = pow(I[2],i-1,Q)
        b = pow(I[2],i-1,Q)
        print(((1 -  w - b)%Q*I[2]%Q + w)%Q)
    else:
        w += F[i-2]*I[i-1-W]%Q*I[W-1]%Q*pow(I[2],i-1,Q)%Q
        w %= Q
        b += F[i-2]*I[i-1-B]%Q*I[B-1]%Q*pow(I[2],i-1,Q)%Q
        b %= Q
        print(((1 -  w - b)%Q*I[2]%Q + w)%Q)

Submission status: Accepted

Solution code:
# E
B, W = map(int, input().split())

LARGE = 10**9 + 7

# pre compute
modulo = [0]*(2*10**5+1)
modulo[0] = 1
for i in range(1, 2*10**5+1):
    modulo[i] =(5*10**8 + 4) * modulo[i-1] % LARGE

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m    
    
frac_mod = [0]*(2*10**5+1)
frac_inv_mod = [0]*(2*10**5+1)
frac_mod[0] = 1
frac_inv_mod[0] = 1
frac_mod[1] = 1
frac_inv_mod[1] = 1

for i in range(2, 2*10**5+1):
    frac_mod[i] = frac_mod[i-1]*i % LARGE
    frac_inv_mod[i] = frac_inv_mod[i-1]*modinv(i, LARGE) % LARGE

B_lost_list = [0]*(B+W)
W_lost_list = [0]*(B+W)

def nCk_mod(n, k):
    return frac_mod[n]*frac_inv_mod[k]*frac_inv_mod[n-k] % LARGE

for n in range(B, B+W):
    B_lost_list[n] = nCk_mod(n-1, B-1)*modulo[n]
    
for n in range(W, B+W):
    W_lost_list[n] = nCk_mod(n-1, W-1)*modulo[n]
    
# must be B
b = 0
w = 0
for i in range(B+W):
    b = (b + B_lost_list[i]) % LARGE
    w = (w + W_lost_list[i]) % LARGE
    
    print((500000004 + w * 500000004 - b * 500000004) % LARGE)

Submission status: Runtime Error

Solution code:
def main():
    b, w = map(int, input().split())
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    half = pow(2, mod-2, mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod

    h = 1

    A, B, C = 0, 1, 0
    for i in range(1, b+w+1):
        h = h*half % mod
        ans = B
        A = A*2 % mod
        B = B*2 % mod
        C = C*2 % mod
        if i-1 >= b:
            p = nCr(i-1, b)
            ans = (ans-p) % mod
            C = (C+p) % mod
            B = (B-p) % mod
        if i-w-1 >= 0:
            p = nCr(i-1, i-w-1)
            A = (A+p) % mod
            B = (B-p) % mod
        ans = (ans+A) % mod
        print(ans*h % mod)


main()

Submission status: Runtime Error

Solution code:
B, W = map(int, input().split())

MOD = 10 ** 9 + 7
M = 100005
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

rfact = [0] * M
rfact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(M - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD


def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * rfact[n - k] * rfact[k] % MOD


num = [0] * 200005
f = [0] * 200005
for i in range(W):
    q = pow(pow(2, i + B), MOD - 2, MOD) * comb(i + B - 1, B - 1) % MOD
    f[i + B] = q

g = [0] * 200005
for i in range(B):
    q = pow(pow(2, i + W), MOD - 2, MOD) * comb(i + W - 1, W - 1) % MOD
    g[i + W] = q
    num[i + W + 1] = q

pB, pW = 0, 0
for i in range(1, B + W + 1):
    d = 1 - (pB + pW) + 2 * MOD
    d %= MOD
    pB += f[i]
    pB %= MOD
    pW += g[i]
    pW %= MOD

    num[i] += num[i - 1]
    num[i] %= MOD
    print((pow(2, MOD - 2, MOD) * d + num[i]) % MOD)

Submission status: Runtime Error

Solution code:
B, W = map(int, input().split(" "))
MOD = 10 ** 9 + 7

# x * z - MOD * n == y
def calcz(x, y):
    a, b = x, MOD
    syou = []
    while a > 1:
        syou.append(b // a)
        a, b = b % a, a
    syou.reverse()
    dp = [0, 1]
    for i in range(len(syou)):
        dp.append(dp[-1] * (-syou[i]) + dp[-2])
    return (dp[-1] * y) % MOD

%%timeit
p_bl = 0
p_wh = 0
bunbo = 1

btmp = 1
wtmp = 1
print(500000004)
for i in range(1, B + W):
    bunbo = bunbo * 2 % MOD
    if i >= B:
        p_bl = (p_bl * 2 + btmp) % MOD
        if i % 10 == 0:
            btmp = calcz(i - B + 1, btmp * i)
        else:
            btmp = btmp * i // (i - B + 1)
        
    if i >= W:
        p_wh = (p_wh * 2 + wtmp) % MOD
        if i % 10 == 0:
            wtmp = calcz(i - W + 1, wtmp * i)
        else:
            wtmp = wtmp * i // (i - W + 1)
        
    if i < min(B, W):
        print(500000004)
    else:
        bunshi = p_wh + (bunbo - p_bl)
        print(calcz(bunbo * 2, bunshi))

Submission status: Runtime Error

Solution code:
B,W = map(int, input().split())
N = B+W

factorial = [1]
for i in range(N+1):
    factorial.append( factorial[-1] * (i+1) % mod)
# print(factorial)

mod = 10**9+7

de_factorial = [0] * (N+1)
de_factorial[N] = pow(  factorial[N] , mod-2, mod  )

for i in range( N, 0, -1):
    de_factorial[i-1] = de_factorial[i] * i % mod
    
def comb(n,r):
    if n < r: return 0
    if n == r: return 1
    return (factorial[n] * de_factorial[r] * de_factorial[n-r]) % mod


p = [0] * (N+1) # Bを食べきった確率
q = [0] * (N+1) # Wを食べきった確率

de2 = de_factorial[2]
for i in range(1, N+1):
    p[i] = p[i-1] + comb(i-1 ,B-1) * de2 % mod 
    q[i] = q[i-1] + comb(i-1 ,W-1) * de2  % mod 
    de2 = de2 * de_factorial[2] % mod

    tmp = ( q[i-1] + 1-p[i-1] ) * de_factorial[2] % mod
    
    print(tmp)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def get_z(y, x):
    while y % x > 0:
        y += MOD
    return y // x

def simplify(y, x):
    ret = 1
    while y % (1 << ret) == 0:
        ret += 1
    return (y >> (ret - 1), x >> (ret - 1))

def comb(n, k):
    if n < k:
        return 0
    k = min(k, n - k)
    ret = 1
    for i in range(k):
        ret *= (n - i)
        ret //= (i + 1)
    return ret

def make_comb(n, k):
    ret = [0] * n
    ret[k] = 1
    for i in range(k + 1, n):
        ret[i] = (ret[i - 1] * i) // (i - k)
        ret[i] %= MOD
    return ret

def solve(b: int, w: int):
    n = b + w
    bb = 0
    ww = 0
    b_comb = make_comb(n, b - 1)
    w_comb = make_comb(n, w - 1)
    par = 1
    for i in range(1, n + 1):
        other = par - bb - ww
        x = (par << 1) % MOD
        y = other + bb * 2
        #print("bb : %d, ww : %d, other : %d" % (bb, ww, other))
        #print(y, ' / ', x)
        x %= MOD
        y %= MOD
        y, x = simplify(y, x)
        ret = get_z(y, x)
        print(ret)
        bb = (bb * 2 + w_comb[i - 1]) % MOD
        ww = (ww * 2 + b_comb[i - 1]) % MOD
        par = (par * 2) % MOD
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    B = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    solve(B, W)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
b, w = [int(i) for i in input().split()]
p = 10 ** 9 + 7

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

def get_inv(n, p=10**9 + 7):
    inv = [0, 1]
    for i in range(2, n+1):
        inv.append(-(p//i * inv[p%i]) % p)
    return inv

f = fact(10 ** 5)
invf = invfact(10 ** 5, f)

def comb(a, b):
    if a < b:
        return 0
    return f[a] * invf[b] * invf[a-b] % p

P = [[0] * 2 for i in range(b + w + 1)]
B = 0
W = 1
inv_2 = invf[2]

for i in range(1, b + w + 1):
    P[i][B] = P[i - 1][B] + comb(i - 1, b - 1) * inv_2  #i番目になくなってる確率
    P[i][W] = P[i - 1][W] + comb(i - 1, w - 1) * inv_2
    inv_2 = inv_2 * invf[2] % p 
    print((1 - P[i - 1][B] + P[i - 1][W]) * invf[2] % p)

Submission status: Runtime Error

Solution code:
from fractions import Fraction
B, W = map(int, input().split())


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def ExtendedEuclidianAlgorithms(a, b):
    """
    返り値: 自然数a, bの最小公倍数d, ax+by=gcd(a, b)を満たす(x, y)が、
    (d, x, y)のtuple
    d = 1ならxはaの逆元(inverse element)
    """
    d, c1 = a, b
    x0, x1 = 1, 0
    y0, y1 = 0, 1
    while c1 != 0:
        m = d % c1
        q = d // c1
        d, c1 = c1, m
        x0, x1 = x1, (x0 - q * x1)
        y0, y1 = y1, (y0 - q * y1)
    return d, x0, y0


def makeTableMod(N, mod=10 ** 9 + 7):
    fac = [1 for i in range(N)]
    finv = [1 for i in range(N)]
    inv = [1 for i in range(N)]
    for i in range(2, N):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


def binomialCoefficient(N, r, mod=10 ** 9 + 7):
    if N < r:
        return 0
    else:
        return fac[N] * (finv[r] * finv[N - r] % mod) % mod


fac, finv = makeTableMod(B+W)
mod = 10 ** 9 + 7


def unknown(x, y, mod=10**9+7):
    g, a, b = ExtendedEuclidianAlgorithms(x, mod)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return a*y % mod


def plusFraction(frac1, frac2):
    """
    frac: tuple (numerator, denominator)
    """
    b, a = frac1
    d, c = frac2
    g = gcd(a, c)
    nume = b * (c // g) + d * (a // g)
    deno = (a * c) // g
    g = gcd(nume, deno)
    nume //= g
    deno //= g

    return (nume, deno)


P = [(0, 1)]
Q = [(0, 1)]


for i in range(B + W):
    if i == 0:
        print(500000004)
        continue
    p = plusFraction(P[-1], (binomialCoefficient(i-1, B-1, mod), 2**i))
    q = plusFraction(Q[-1], (binomialCoefficient(i-1, W-1, mod), 2**i))
    P.append(p)
    Q.append(q)
    b, a = p[1]-p[0], p[1]
    d, c = q
    g = gcd(a, c)
    nume = b * (c // g) + d * (a // g)
    deno = ((a * c) // g) * 2
    g = gcd(nume, deno)
    nume //= g
    deno //= g
    ans = unknown(deno, nume)
    print(ans)

Submission status: Runtime Error

Solution code:
mod = 10**9+7

n,m = map(int,input().split())

s = list(map(int,input().split()))

s.sort()

s = [None] + s

dp = [[0 for i in range(m+1)] for j in range(n+1)]
dp[1] = [i % s[1] for i in range(m+1)]

for i in range(2,n+1):
    for j in range(m+1):
        dp[i][j] = (dp[i-1][j] * (i-1) + dp[i-1][j%s[i]]) % mod
print(dp[n][m])

Submission status: Runtime Error

Solution code:

def comb_(n,k):
    return fact(n)*fact_inv(k)*fact_inv(n-k)*pow(2,(n+1)*(mod-2),mod)%mod

f_B = defaultdict(lambda:pow(2,mod-2,mod))
f_W = defaultdict(lambda:pow(2,mod-2,mod))
g = defaultdict(lambda:pow(2,W*(mod-2),mod))

for i in range(B,B+W):
    f_B[i+1] = f_B[i]-comb_(i-1,B-1)*pow(2,mod-2,mod)
    f_B[i+1] %= mod

for i in range(W,B+W):
    f_W[i+1] = f_W[i]-comb_(i-1,W-1)*pow(2,mod-2,mod)
    f_W[i+1] %= mod

for i in range(W+1,B+W):
    g[i+1] = g[i] + comb_(i-1,W-1)
    g[i+1] %= mod

for i in range(1,B+W+1):
    if i < W+1:
        print(f_B[i])
    else:
        print((f_B[i]+f_W[i]+g[i]-pow(2,mod-2,mod))%mod)

Submission status: Runtime Error

Solution code:
b,w=map(int,input().split());gcd=lambda a,b:gcd(max(a,b)%min(a,b),min(a,b))if max(a,b)%min(a,b)else min(a,b);p=f(b+w)//f(b)//f(w)
def g(x,y):print((1000000008*x)//y)
q=2
for i in range(min(b,w)):g(1,2);q*=2
x,y=1,2
for i in range(b+w-min(b,w)-1):bunbo=q;bunsi=q//2+1;x,y=bunbo,bunsi;g(y,x);q*=2
g(y,x)

Submission status: Runtime Error

Solution code:
b,w=map(int,input().split())
from math import factorial as f
gcd=lambda a,b:gcd(max(a,b)%min(a,b),min(a,b))if max(a,b)%min(a,b)else min(a,b)
from math import gcd
p=f(b+w)//f(b)//f(w)
def g(x,y):print((1000000008*x)//y)
q=2
for i in range(min(b,w)):
    g(1,2)
    q*=2
x,y=1,2
for i in range(b+w-min(b,w)-1):
 bunbo=q
 bunsi=q//2+1
 x,y=bunbo,bunsi
 g(y,x)
 q*=2
g(y,x)

Submission status: Runtime Error

Solution code:
b,w=map(int,input().split())
from math import factorial as f
from math import gcd
p=f(b+w)//f(b)//f(w)
def 確率(x,y):print((1000000008*x)//y)
q=2
for i in range(min(b,w)):
    確率(1,2)
    q*=2
x,y=1,2
for i in range(b+w-min(b,w)-1):
 bunbo=q
 bunsi=q//2+1
 x,y=bunbo,bunsi
 確率(y,x)
 q*=2
確率(y,x)

Submission status: Runtime Error

Solution code:
B,W=map(int,input().split())
mod=10**9+7
kaijo=[1]
for i in range(1,1+B+W):
    kaijo.append((kaijo[-1])*i%mod)
from collections import deque
gyaku=deque()
gyaku.append(pow(kaijo[B+W],mod-2,mod))
for i in range(B+W,0,-1):
    gyaku.appendleft((gyaku[0]*i)%mod)
def conb(a,b):
    return (kaijo[a]*gyaku[a-b]*gyaku[b])%mod
Blost,Wlost=[0],[0]
Xdiv=[pow(pow(2,i,mod),mod-2,mod) for i in range(1+B+W)]
for k in range(1,B+W):
    if k<B:
        Blost.append(0)
    elif k>=B:
        Blost.append((Blost[-1]++conb(k-1,B-1)*Xdiv[k])%mod)
    if k<W:
        Wlost.append(0)
    elif k>=W:
        Wlost.append((Wlost[-1]+conb(k-1,W-1)*Xdiv[k])%mod)
Blost.append(1)
Wlost.append(1)
for k in range(1,B+W+1):
    print(((1+Wlost[k-1]-Blost[k-1])*two)%mod)

Submission status: Runtime Error

Solution code:
#a,b,c = [int(i) for i in input().split()]

import sys
input = sys.stdin.readline

SIZE=200002; 
MOD = 10**9+7
2bai= 500000000+4

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0



b,w = [int(i) for i in input().split()]

ans = [0]*(b+1)
ans[x] = 1

c = min(b,w)
for i in [0]*c:
    print(2bai)

ans = 2bai
for i in range(c,b+w+1):
    ans += pow(2,i-1,MOD)*(choose(i-1,i-1-w) - choose(i-1,b-1)
    ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
print “500000004”
print “750000006”
print “750000006”