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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 2*10**5 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# 足す時は0~iまで一律に足し、返すのはi番目の値
class imosBIT():
    def __init__(self, N):
        self.N = N+1
        self.bit = [0 for _ in range(self.N+1)]
    
    def __str__(self):
        ret = []
        for i in range(1, self.N+1):
            ret.append(self.__getitem__(i))
        return "[" + ", ".join([str(a) for a in ret]) + "]"

    def __getitem__(self, i):
        i += 1
        s = 0
        while i <= self.N:
            s = (s + self.bit[i]) % mod
            i += i & -i
        return s

    def add(self, i, x):
        i += 1
        while i > 0:
            self.bit[i] = (self.bit[i] + x) % mod
            i -= i & -i
    
    # (i, N]に全てたす
    def addover(self, i, x):
        self.add(self.N-1, x)
        self.add(i, -x)

B, W = map(int, input().split())
N = B+W
Abit = imosBIT(N+1)
Bbit = imosBIT(N+1)
inv2 = pow(2, mod-2, mod)
t = inv2
for i in range(N):
    if i+1 >= W:
        Abit.addover(i, t*cmb(i, W-1)%mod)
    if i+1 >= B:
        Bbit.addover(i, t*cmb(i, B-1)%mod)
    t = t*inv2 % mod

for i in range(N):
    ans = (1 + Abit[i] - Bbit[i]) * inv2 % mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
B, W = map(int, input().split())
mod = int(1e9) + 7
def doubling(n, m):
  y = 1
  base = n
  while m != 0:
    if m % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    m //= 2
  return y
def inved(a):
  x, y, u, v, k, l = 1, 0, 0, 1, a, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod

fact = [1 for i in range(B+W+1)]
invf = [1 for i in range(B+W+1)]
for i in range(B+W):
  fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(B+W, 0, -1):
  invf[i-1] = (invf[i] * i) % mod
bina = [1 for i in range(B+W+1)]
invb = [1 for i in range(B+W+1)]
for i in range(B+W):
  bina[i+1] = (bina[i] * 2) % mod
invb[-1] = inved(bina[-1])
for i in range(B+W, 0, -1):
  invb[i-1] = (invb[i] * 2) % mod
for i in range(1, B + W + 1):
  S = 0
  for j in range(min(i, B)):
    S += (invf[j] * invf[i-1-j]) % mod
    S %= mod
  for j in range(max(i-W, 0)):
    S += (invf[j] * invf[i-1-j]) % mod
    S %= mod
  S *= (fact[i-1] * invb[i]) % mod
  S %= mod
  print(S)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 5 * 3)


def nCr(n, r):
    return fac[n] * pow(fac[n - r], MOD - 2, MOD) * pow(fac[r], MOD - 2, MOD) % MOD


for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
b, w = map(int, input().split())
n = b + w
p = [0] * n
q = [0] * n
for i in range(b, n):
    p[i] = (p[i - 1] + nCr(i - 1, b - 1) *
            pow(pow(2, i, MOD), MOD - 2, MOD)) % MOD
for i in range(w, n):
    q[i] = (q[i - 1] + nCr(i - 1, w - 1) *
            pow(pow(2, i, MOD), MOD - 2, MOD)) % MOD
for i in range(n):
    print((q[i] + (1 - p[i] - q[i]) * pow(2, MOD - 2, MOD)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

b,w=map(int,input().split())
x=0
y=0
for i in range(1,b+w+1):
  x=(x*2+cmb(i-2,b-1))%mod
  y=(y*2+cmb(i-2,w-1))%mod
  print((mod+pow(2,i-1,mod)-x+y)*pow(pow(2,i,mod),mod-2,mod)%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction

class Combination:
    '''計算量：階乗・逆元テーブルの作成O(N)
       nCkを求めるO(1)'''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]

    def combination(self, k, r):
        '''kCrを求める'''
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


b, w = map(int,input().split())
MOD = 10**9 + 7
comb = Combination(b+w, MOD)

#黒が(b+w-i)個残る確率 := pb
#白が(b+w-i)個残る確率 := pw
pb = [0]*(b+w+1)
pw = [0]*(b+w+1)

for i in range(b+w):
    if b+w-i > b:
        pb[b+w-i] = 0
        result_b = Fraction(0)
    else:
        result_b = Fraction(pb[b+w-i+1]) \
                 + Fraction(1, pow(2, i, MOD)) * Fraction(comb.combination(i-1, w-1) % MOD)
        pb[b+w-i] = Fraction(result_b.numerator % MOD, result_b.denominator % MOD)
        
    if b+w-i > w:
        pw[b+w-i] = 0
        result_w = Fraction(0)
    else:
        result_w = Fraction(pw[b+w-i+1]) \
                 + Fraction(1, pow(2, i, MOD)) * Fraction(comb.combination(i-1, b-1) % MOD)
        pw[b+w-i] = Fraction(result_w.numerator % MOD, result_w.denominator % MOD)
        
    ans = Fraction(result_b) \
          + Fraction(1, 2) * (Fraction(1) - Fraction(result_b) - Fraction(result_w))
    y = ans.numerator % MOD
    x = ans.denominator % MOD
    
    print((y * pow(x, MOD-2, MOD)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9 + 7
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

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

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

def pw(x,e):
    if e==0:
        return 1
    elif e%2==0:
        return (pw(x,e//2)**2)%R
    else:
        return (x * pw(x,e//2)**2)%R

def rmod(i,qb,qw, inv2):
    numer = (pw(2,i) - qb + qw)
    iden = pw(inv2, i+1)
    ddprint("num {} idn {}".format(numer, iden))
    return (numer*iden)%R

b,w = inm()
ddprint("b {} w {}".format(b,w))
inv2 = modinv(2,R)
fact = [1] * (b+w+2)
for i in range(2,b+w+1):
    fact[i] = (i*fact[i-1])%R
ifact = [1] * (b+w+2)
ifact[b+w] = modinv(fact[b+w],R)
for i in range(b+w-1,0,-1):
    ifact[i] = ((i+1)*ifact[i+1])%R
cb = cw = 1
qb = qw = 0
print(500000004)
for i in range(1,b+w):
    qb = 0 if i<b else 1 if i==b else (2*qb+cb) % R
    qw = 0 if i<w else 1 if i==w else (2*qw+cw) % R
    cb = 1 if i<b else (fact[i]*ifact[b-1]*ifact[i-b+1]) % R
    cw = 1 if i<w else (fact[i]*ifact[w-1]*ifact[i-w+1]) % R
    ddprint("i {} cb {} cw {} qb {} qw {}".format(i,cb,cw,qb,qw))
    print(rmod(i,qb,qw,inv2))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9 + 7
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

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

# return y s.t. x*y mod p == 1
@lru_cache(maxsize=None)
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

@lru_cache(maxsize=None)
def modinv2(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a

@lru_cache(maxsize=None)
def modr(x):
    return x%R

def rmod(i,qb,qw):
    numer = (two2i[i] - qb + qw)
    denom = two2i[i+1]
    iden = modinv2(denom, R)
    ddprint("num {} den {} idn {}".format(numer, denom, iden))
    return (numer*iden)%R

b,w = inm()
ddprint("b {} w {}".format(b,w))
two2i = [1] * (b+w+2)
for i in range(1,b+w+2):
    x = (2*two2i[i-1])
    two2i[i] = x if x < R else x-R
cb = cw = 1
qb = qw = 0
print(500000004)
for i in range(1,b+w):
    qb = 0 if i<b else 1 if i==b else (2*qb+cb) % R
    qw = 0 if i<w else 1 if i==w else (2*qw+cw) % R
    cb = 1 if i<b else ((cb*i) * modinv2(i-b+1, R)) % R
    cw = 1 if i<w else ((cw*i) * modinv2(i-w+1, R)) % R
    ddprint("i {} cb {} cw {} qb {} qw {}".format(i,cb,cw,qb,qw))
    print(rmod(i,qb,qw))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9 + 7
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

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

# return y s.t. x*y mod p == 1
@lru_cache(maxsize=None)
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

@lru_cache(maxsize=None)
def modr(x):
    return x%R

def rmod(i,qb,qw):
    numer = (two2i[i] - qb + qw)
    denom = two2i[i+1]
    iden = modinv(denom, R)
    ddprint("num {} den {} idn {}".format(numer, denom, iden))
    return (numer*iden)%R

b,w = inm()
ddprint("b {} w {}".format(b,w))
two2i = [1] * (b+w+2)
for i in range(1,b+w+2):
    x = (2*two2i[i-1])
    two2i[i] = x if x < R else x-R
cb = cw = 1
qb = qw = 0
print(500000004)
for i in range(1,b+w):
    qb = 0 if i<b else 1 if i==b else (2*qb+cb) % R
    qw = 0 if i<w else 1 if i==w else (2*qw+cw) % R
    cb = 1 if i<b else ((cb*i) * modinv(i-b+1, R)) % R
    cw = 1 if i<w else ((cw*i) * modinv(i-w+1, R)) % R
    ddprint("i {} cb {} cw {} qb {} qw {}".format(i,cb,cw,qb,qw))
    print(rmod(i,qb,qw))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9 + 7
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

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

# return y s.t. x*y mod p == 1
@lru_cache(maxsize=None)
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

def rmod(i,qb,qw):
    numer = (two2i[i] - qb + qw) % R
    denom = two2i[i+1]
    iden = modinv(denom, R)
    ddprint("num {} den {} idn {}".format(numer, denom, iden))
    return (numer*iden)%R

b,w = inm()
ddprint("b {} w {}".format(b,w))
two2i = [1] * (b+w+2)
for i in range(1,b+w+2):
    x = (2*two2i[i-1])
    two2i[i] = x if x < R else x-R
cb = cw = 1
qb = qw = 0
print(500000004)
for i in range(1,b+w):
    qb = 0 if i<b else 1 if i==b else (2*qb+cb) % R
    qw = 0 if i<w else 1 if i==w else (2*qw+cw) % R
    cb = 1 if i<b else ((cb*i) * modinv(i-b+1, R)) % R
    cw = 1 if i<w else ((cw*i) * modinv(i-w+1, R)) % R
    ddprint("i {} cb {} cw {} qb {} qw {}".format(i,cb,cw,qb,qw))
    print(rmod(i,qb,qw))

Submission status: Time Limit Exceeded

Solution code:
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9 + 7
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

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

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

def rmod(i,qb,qw):
    numer = (two2i[i] - qb + qw) % R
    denom = two2i[i+1]
    iden = modinv(denom, R)
    ddprint("num {} den {} idn {}".format(numer, denom, iden))
    return (numer*iden)%R

b,w = inm()
ddprint("b {} w {}".format(b,w))
two2i = [1] * (b+w+2)
for i in range(1,b+w+2):
    x = (2*two2i[i-1])
    two2i[i] = x if x < R else x-R
cb = cw = 1
qb = qw = 0
print(500000004)
for i in range(1,b+w):
    qb = 0 if i<b else 1 if i==b else (2*qb+cb) % R
    qw = 0 if i<w else 1 if i==w else (2*qw+cw) % R
    cb = 1 if i<b else ((cb*i) * modinv(i-b+1, R)) % R
    cw = 1 if i<w else ((cw*i) * modinv(i-w+1, R)) % R
    ddprint("i {} cb {} cw {} qb {} qw {}".format(i,cb,cw,qb,qw))
    print(rmod(i,qb,qw))

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9 + 7
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

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

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

def rmod(i,qb,qw):
    numer = (two2i[i] - qb + qw) % R
    denom = two2i[i+1]
    iden = modinv(denom, R)
    ddprint("num {} den {} idn {}".format(numer, denom, iden))
    return (numer*iden)%R

b,w = inm()
ddprint("b {} w {}".format(b,w))
two2i = [1] * (b+w+2)
for i in range(1,b+w+2):
    two2i[i] = (2*two2i[i-1]) % R
cb = cw = 1
qb = qw = 0
print(500000004)
for i in range(1,b+w):
    qb = 0 if i<b else 1 if i==b else (2*qb+cb) % R
    qw = 0 if i<w else 1 if i==w else (2*qw+cw) % R
    cb = 1 if i<b else ((cb*i) * modinv(i-b+1, R)) % R
    cw = 1 if i<w else ((cw*i) * modinv(i-w+1, R)) % R
    ddprint("i {} cb {} cw {} qb {} qw {}".format(i,cb,cw,qb,qw))
    print(rmod(i,qb,qw))

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9 + 7
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

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

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

def rmod(i,qb,qw):
    numer = 2**i - qb + qw
    denom = 2**(i+1)
    iden = modinv(denom, R)
    ddprint("num {} den {} idn {}".format(numer, denom, iden))
    return (numer*iden)%R

b,w = inm()
ddprint("b {} w {}".format(b,w))
cb = cw = 1
qb = qw = 0
print(500000004)
for i in range(1,b+w):
    qb = 0 if i<b else 1 if i==b else (2*qb+cb)
    qw = 0 if i<w else 1 if i==w else (2*qw+cw)
    cb = 1 if i<b else (cb*i)//(i-b+1)
    cw = 1 if i<w else (cw*i)//(i-w+1)
    ddprint("i {} cb {} cw {} qb {} qw {}".format(i,cb,cw,qb,qw))
    print(rmod(i,qb,qw))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
fact = [1]
invfact = [1]
for i in range(1,2*10**5 + 100):
    fact.append((fact[i-1] * i) % MOD)
    invI = pow(i,MOD-2,MOD)
    invfact.append((invfact[i-1] * invI) % MOD)

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

pcSum = [1 for _ in range(B+W+1)]
qcSum = [1 for _ in range(B+W+1)]
def modComb(n,m):
    if m < 0 or m > n: return(0)
    ans = fact[n] * invfact[m] 
    ans %= MOD
    ans *= invfact[n-m]
    ans %= MOD
    return(ans)

for i in range(B+W-1):
    pcSum[i+1] = 2*pcSum[i] - modComb(i,B-1)
    pcSum[i+1] %= MOD
    if (i+1-W) <= B-1:
        qcSum[i+1] = 2*qcSum[i] - modComb(i,B-1) - modComb(i,i+1-W)
        qcSum[i+1] %= MOD
    else:
        qcSum[i+1] = 0

p = []
q = []
for i in range(B+W):
    coefficient = pow(2,i*(MOD-2),MOD)
    pvalue = pcSum[i] * coefficient
    pvalue %= MOD
    p.append(pvalue)
    qvalue = qcSum[i] * coefficient
    qvalue %= MOD
    q.append(qvalue)
invTwo = pow(2,MOD-2,MOD)
for i in range(N):
    answer = p[i] - invTwo * q[i]
    answer %= MOD
    print(answer)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7
M = 200005
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: Time Limit Exceeded

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

MOD = 10**9+7
facts = [1,1]
invs = [1,1]
invfacts = [1,1]
for ind in range(1, B+W):
    i = ind+1
    facts += [ facts[-1]*i % MOD ]
    invs += [ -(MOD//i)*invs[MOD%i] % MOD ]
    invfacts += [ invfacts[-1]*invs[i] % MOD ]

y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
pow2 = 1
inv2i = 1
for i in range(B+W):
    y_pi = 0 if i < B else 2*y_pi + ((facts[i-1]*invfacts[i-B] % MOD)*invfacts[B-1] % MOD)
    y_qi = 0 if i < W else 2*y_qi + ((facts[i-1]*invfacts[i-W] % MOD)*invfacts[W-1] % MOD)
    invxi = inv2i * invs[2] % MOD
    yi = (pow2-y_pi+y_qi) % MOD
    z = yi*invxi % MOD
    print(z)
    pow2 = pow2*2 %MOD
    inv2i = invxi

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
combB1 = 0
combW1 = 0
y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
pow2list = [1]
invmod = {}
for i in range(B+W):
    pow2list += [pow2list[-1]*2 %MOD]
    y_pi = 0 if i < B else 2*y_pi + combB1
    y_qi = 0 if i < W else 2*y_qi + combW1
    xi = pow2list[i+1]
    if xi in invmod:
        invxi = invmod[xi]
    else:
        invxi = pow(xi, MOD-2, MOD)
        invmod[xi] = invxi
    yi = (pow2list[i]-y_pi+y_qi) % MOD
    z = yi*invxi % MOD
    print(int(z))
    if i < B-1:
        combB1 = 0
    elif i == B-1:
        combB1 = 1
    else:
        if i-B+1 in invmod:
            invB = invmod[i-B+1]
        else:
            invB = pow(i-B+1, MOD-2, MOD)
            invmod[i-B+1] = invB
        combB1 = combB1*i*invB % MOD
    if i < W-1:
        combW1 = 0
    elif i == W-1:
        combW1 = 1
    else:
        if i-W+1 in invmod:
            invW = invmod[i-W+1]
        else:
            invW = pow(i-W+1, MOD-2, MOD)
            invmod[i-W+1] = invW
        combW1 = combW1*i*invW % MOD

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
def MakeCombList(n,r, MOD): #iCrをi=0...nまで
    ret = []
    for i in range(n):
        if i < r:
            ret = ret+[0]
        elif i == r:
            ret = ret+[1]
        else:
            ret = ret+[ int(ret[-1]*(i)/(i-r)) % MOD]
    return ret
combB1 = MakeCombList(B+W, B-1, MOD)
combW1 = MakeCombList(B+W, W-1, MOD)

y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
for i in range(B+W):
    y_pi = 0 if i < B else 2*y_pi + combB1[i-1] 
    y_qi = 0 if i < W else 2*y_qi + combW1[i-1]
    xi = pow(2,i+1,MOD)
    yi = (pow(2,i,MOD)-y_pi+y_qi) % MOD
    z = yi*pow(xi, MOD-2, MOD) % MOD
    print(z)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
def MakeCombList(n,r, MOD): #iCrをi=0...nまで
    ret = []
    for i in range(n):
        if i < r:
            ret = ret+[0]
        elif i == r:
            ret = ret+[1]
        else:
            ret = ret+[ int(ret[-1]*(i)/(i-r)) % MOD]
    return ret
combB1 = MakeCombList(B+W, B-1, MOD)
combW1 = MakeCombList(B+W, W-1, MOD)

pow2list = [1]
y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
for i in range(B+W):
    pow2list += [pow2list[-1]*2 %MOD]
    y_pi = 0 if i < B else 2*y_pi + combB1[i-1] 
    y_qi = 0 if i < W else 2*y_qi + combW1[i-1]
    xi = pow2list[i+1]
    yi = (pow2list[i]-y_pi+y_qi) % MOD
    z = yi*pow(xi, MOD-2, MOD) % MOD
    #print("{}/{}: {}".format(yi,xi,z))
    print(z)

Submission status: Time Limit Exceeded

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

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
        btmp = calcz(i - B + 1, btmp * i)
        
    if i >= W:
        p_wh = (p_wh * 2 + wtmp) % MOD
        wtmp = calcz(i - W + 1, wtmp * i)
        
    if i < min(B, W):
        print(500000004)
    else:
        bunshi = p_wh + (bunbo - p_bl)
        print(calcz(bunbo * 2, bunshi))

Submission status: Time Limit Exceeded

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

p_bl = [0 for i in range(B+W)]
p_wh = [0 for i in range(B+W)]
bunbo = [1]

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

Submission status: Time Limit Exceeded

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

p_bl = [0 for i in range(B+W)]
p_wh = [0 for i in range(B+W)]
bunbo = [1]

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

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int

def get_z(y, x): # y / x
    inv_x = pow(x, MOD - 2, MOD)
    return y * inv_x % MOD

def _get_z(y, x): # y / x
    #inv_x = pow(x, MOD - 2, MOD)
    #return y * inv_x % MOD
    while y % x > 0:
        y += MOD
    return y // x

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def reduce(y, x):
    tmp = gcd(x, y)
    return (y // tmp, x // tmp)

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
    for i in range(k + 1, n):
        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):
        #print(' ======== i: %d ==============' % i)
        other = par - bb - ww
        x = (par * 2) % MOD
        y = (other + bb * 2) % MOD
        #x = (par * 2)
        #y = other + bb * 2
        #print("bb : %d, ww : %d, other : %d" % (bb, ww, other))
        #print(y, ' / ', x)
        #y, x = reduce(y, x)
        ret = get_z(y, x)
        print(ret)
        #bb = (bb * 2 + w_comb[i - 1])
        #ww = (ww * 2 + b_comb[i - 1])
        #par = (par * 2)
        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: Time Limit Exceeded

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

MOD = 1000000007  # type: int

def get_z(y, x): # y / x
    inv_x = pow(x, MOD - 2, MOD)
    return y * inv_x % MOD

def _get_z(y, x): # y / x
    #inv_x = pow(x, MOD - 2, MOD)
    #return y * inv_x % MOD
    while y % x > 0:
        y += MOD
    return y // x

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def reduce(y, x):
    tmp = gcd(x, y)
    return (y // tmp, x // tmp)

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):
        #print(' ======== i: %d ==============' % i)
        other = par - bb - ww
        #x = (par * 2) % MOD
        #y = (other + bb * 2) % MOD
        x = (par * 2)
        y = other + bb * 2
        #print("bb : %d, ww : %d, other : %d" % (bb, ww, other))
        #print(y, ' / ', x)
        #y, x = reduce(y, x)
        ret = get_z(y, x)
        print(ret)
        bb = (bb * 2 + w_comb[i - 1])
        ww = (ww * 2 + b_comb[i - 1])
        par = (par * 2)
        #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()