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:
#!/usr/bin/env python3
import math
import operator as op
import os
import sys
from functools import reduce
from io import BytesIO, IOBase

sys.stdout, stream = IOBase(), BytesIO()
sys.stdout.flush = lambda: os.write(1, stream.getvalue()) and not stream.truncate(0) and stream.seek(0)
sys.stdout.write = lambda s: stream.write(s.encode())

input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

MOD = 10**9 + 7
MODF = float(MOD)

MAGIC = 6755399441055744.0
SHRT = 65536.0

MODF_INV = 1.0 / MODF
SHRT_INV = 1.0 / SHRT

fround = lambda x: (x + MAGIC) - MAGIC
fmod = lambda a: a - MODF * fround(MODF_INV * a)
fmul = lambda a, b, c=0.0: fmod(fmod(a * SHRT) * fround(SHRT_INV * b) + a * (b - SHRT * fround(b * SHRT_INV)) + c)


def fpow(x, y):
    if y == 0:
        return 1.0

    res = 1.0
    while y > 1:
        if y & 1 == 1:
            res = fmul(res, x)
        x = fmul(x, x)
        y >>= 1

    return fmul(res, x)


def factorial_p(n):
    ans = 1
    if n <= MOD // 2:
        for i in range(1, n + 1):
            ans = fmul(ans, i)
    else:
        for i in range(1, MOD - n):
            ans = fmul(ans, i)
        ans = fpow(ans, MOD - 2)

        if n % 2 == 0:
            ans = MOD - ans

    return ans


def nCr_p(n, r):
    ans = 1.0
    while (n != 0) or (r != 0):
        ans = fmul(fmul(fmul(ans, factorial_p(n)), fpow(factorial_p(r), MOD - 2)), fpow(factorial_p(n - r), MOD - 2))
        n //= MOD
        r //= MOD

    return ans


def main():
    b, w = map(int, input().split())

    inv_2 = [1.0] * (b + w)
    for i in range(b + w - 1):
        inv_2[i + 1] = fmul(inv_2[i], 500000004.0)

    for i in range(1, b + w + 1):
        res = 0.0

        for j in range(max(i - b, 0), min(w, i)):
            res += fmul(nCr_p(i - 1, j), inv_2[i])
        for j in range(w, i):
            res += fmul(nCr_p(i - 1, j), inv_2[i - 1])

        print(int(res) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
def egcd(a, b):
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,mod)[0]%mod
N=2*10**5+10
B,W=map(int,input().split())
Blist=[0 for i in range(N+1)]
Wlist=[0 for i in range(N+1)]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Exp2=[0 for i in range(N+1)]
Fact[0]=1;Finv[0]=1
Exp2[0]=1
for i in range(N):
    Exp2[i+1]=(Exp2[i]*2)%mod
for i in range(N):
    Fact[i+1]=(Fact[i]*(i+1))%mod
    Finv[i+1]=inv(Fact[i+1])
def C(n,k):
    if k<0 or n<k:
        return 0
    else:
        return (Finv[k]*(Fact[n]*Finv[n-k])%mod)%mod
Blist[0]=1;Wlist[0]=1
for i in range(N):
    Blist[i+1]=(2*Blist[i]-C(i,B-1))%mod
    Wlist[i+1]=(2*Wlist[i]-C(i,W-1))%mod
#print(Blist[:B+W])
#print(Wlist[:B+W])
ans=[0 for i in range(B+W)]
for i in range(B+W):
    ans[i]=(Blist[i]-Wlist[i]+Exp2[i])%mod
    ans[i]=(ans[i]*inv(Exp2[i+1]))%mod
for line in ans:
    print(line)

Submission status: Accepted

Solution code:
b,w=map(int,input().split())
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
t1,t2=0,0
for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  if i-b>0:
    t1*=2
    t1%=mod
    t1+=cmb(i-2,b-1,mod)
    t1%=mod
    tmp=t1*pow(2,mod-1-i,mod)
    tmp%=mod
    t-=tmp
    t%=mod
  if i-w>0:
    t2*=2
    t2%=mod
    t2+=cmb(i-2,w-1,mod)
    t2%=mod
    tmp=t2*pow(2,mod-1-i,mod)
    tmp%=mod
    t+=tmp
    t%=mod
  print(t)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


b, w = LI()
n = b + w
fac = [1] * (n + 1)
inv = [1] * (n + 1)
two_inv = [0] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


two_inv[n] = pow(pow(2, n, mod), mod-2, mod)
for j in range(n-1, -1, -1):
    two_inv[j] = two_inv[j+1] * 2 % mod

def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


LB = [0] * (n + 1)
LW = [0] * (n + 1)
for i in range(n + 1):
    LB[i] = two_inv[i] * comb(i - 1, b - 1) % mod

for j in range(n + 1):
    LW[j] = two_inv[j] * comb(j - 1, w - 1) % mod

for k in range(1, n + 1):
    LB[k] = (LB[k - 1] + LB[k]) % mod
    LW[k] = (LW[k - 1] + LW[k]) % mod



for l in range(1, n + 1):
    print(((1 - LB[l - 1] - LW[l - 1]) * two_inv[1] + LW[l - 1]) % mod)

Submission status: Accepted

Solution code:
b,w = map(int,input().split())
mod = 10**9 + 7

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 2 * 10**5 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod



ans = []
ex2 = 1
b_end = 0
w_end = 0
n = b+w
for i in range(n):
    if(i >= b):
        b_end = (b_end*2 + com(i-1,i-b) )%mod
    if(i >= w):
        w_end = (w_end*2 + com(i-1,i-w) )%mod

    bw = (ex2 - b_end - w_end)% mod
    ex2 = (ex2*2)%mod
    ans.append( (w_end*2 + bw) * pow(ex2,mod-2,mod) % mod )

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
b, w = map(int, input().split())
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
n = b + w + 10
inv = [1] * (n + 1)
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n):
    inv[i] = ((inv[i - 1] % 2) * mod + inv[i - 1]) // 2
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
p, q = 0, 0
for i in range(b + w):
    if i >= b:
        p *= 2
        p += comb(i - 1, b - 1)
        p %= mod
    if i >= w:
        q *= 2
        q += comb(i - 1, w - 1)
        q %= mod
    print(((q - p) * inv[i + 1] + inv[1]) % mod)

Submission status: Accepted

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    B, W = LI()
    N = B+W
    C = combination(N,mod)

    ans = [0]*N
    inv_2 = pow(2,mod-2,mod)
    now_W = 0
    now_B = 0
    for i in range(N):
        cur = inv_2
        if i>=W:
            #print(i)
            now_W = now_W*2 + C.comb(i-1, i-W)
            cur += pow(inv_2,i+1,mod)*now_W
        if i>=B:
            now_B = now_B * 2 + C.comb(i - 1, i - B)
            cur -= pow(inv_2, i + 1, mod) * now_B
        now_B %= mod
        now_W %= mod
        cur %= mod
        ans[i] = cur

    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
M=10**9+7;B,W=map(int,input().split());F=[1];I=[1];p=q=0;C=lambda n,k:F[n]*pow(F[k]*F[n-k],M-2,M)if n>=k else 0
for i in range(1,B+W+1):F+=[F[-1]*i%M];I+=[I[-1]+I[-1]%2*M>>1];print((1-p+q)*I[1]%M);p+=C(i-1,B-1)*I[i];q+=C(i-1,W-1)*I[i]

Submission status: Accepted

Solution code:
def main():
    b, w = map(int, input().split())
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 2*(10**5)+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: Accepted

Solution code:
def cmb(n, r, mod):#コンビネーションの高速計算　
    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 )

import sys
write=sys.stdout.write

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

p=[1]
for i in range(1,B+W+1) :
    p.append((p[-1]*inverse[2])%mod)

BD=[0]
for i in range(1,B+W+1):
    t=(BD[-1]+cmb(i-1,B-1,mod)*p[i])%mod
    BD.append(t)

WD=[0]
for i in range(1,B+W+1):
    t=(WD[-1]+cmb(i-1,W-1,mod)*p[i])%mod
    WD.append(t)

for i in range(1,B+W+1):
    ans=(1-BD[i-1]-WD[i-1])*p[1]+WD[i-1]
    ans%=mod
    write(str(ans)+"\n")

Submission status: Accepted

Solution code:
def cmb(n, r, mod):#コンビネーションの高速計算　
    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())

p=[1]
for i in range(1,B+W+1) :
    p.append((p[-1]*inverse[2])%mod)

BD=[0]
for i in range(1,B+W+1):
    t=(BD[-1]+cmb(i-1,B-1,mod)*p[i])%mod
    BD.append(t)

WD=[0]
for i in range(1,B+W+1):
    t=(WD[-1]+cmb(i-1,W-1,mod)*p[i])%mod
    WD.append(t)

for i in range(1,B+W+1):
    ans=(1-BD[i-1]-WD[i-1])*p[1]+WD[i-1]
    ans%=mod
    print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] % md * ifac[com_n - com_r] % md

# combinationの準備
# md>n_maxの条件
md = 10 ** 9 + 7
n_max = 200005
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md
half=[1]*n_max
half[n_max-1]=pow(pow(2,n_max-1,md),md-2,md)
for i in range(n_max-2,0,-1):half[i]=half[i+1]*2%md

memo={}
# 色c（代入するのは個数）がt回でなくなる確率
def p0(t,c):
    if t<c:return 0
    if (t,c) in memo:return memo[t,c]
    res=p0(t-1,c)+half[t]*nCr(t-1,c-1)
    res=memo[t,c]=res%md
    return res

def main():
    b,w=MI()
    for i in range(b+w):
        ans=p0(i,w)+(1-p0(i,b)-p0(i,w))*half[1]
        print(ans%md)

main()

Submission status: Accepted

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
if B == W:
  for i in range(B+W):
    print(invf[2])
elif B > W:
  for i in range(W):
    print(invf[2])
  P = invf[2]
  for i in range(W+1, B+1):
    F = (fact[i-2] * invf[i-1-W] * invf[W-1]) % mod
    F *= invb[i]
    F %= mod
    F += P
    F %= mod
    print(F)
    P = F
  for i in range(B+1, B+W+1):
    F = invf[i-1-B] * invf[B-1]
    F %= mod
    F *= fact[i-2]
    F %= mod
    F *= mod - 1
    F += (fact[i-2] * invf[i-1-W] * invf[W-1]) % mod
    F %= mod
    F *= invb[i]
    F %= mod
    F += P
    F %= mod
    print(F)
    P = F
elif B < W:
  for i in range(B):
    print(invf[2])
  P = invf[2]
  for i in range(B+1, W+1):
    F = (fact[i-2] * invf[i-1-B] * invf[B-1]) % mod
    F *= mod - 1
    F %= mod
    F *= invb[i]
    F %= mod
    F += P
    F %= mod
    print(F)
    P = F
  for i in range(W+1, B+W+1):
    F = invf[i-1-B] * invf[B-1]
    F %= mod
    F *= fact[i-2]
    F %= mod
    F *= mod - 1
    F += (fact[i-2] * invf[i-1-W] * invf[W-1]) % mod
    F %= mod
    F *= invb[i]
    F %= mod
    F += P
    F %= mod
    print(F)
    P = F

Submission status: Accepted

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
t = pow(2, MOD - 2, MOD)
for i in range(n):
    print((q[i] + (1 - p[i] - q[i]) * t) % MOD)

Submission status: Accepted

Solution code:
b,w = map(int,input().split())
flg = 0
if b>w:
  flg = 1
  b,w = w,b
elif b == w:
  for _ in range(b+w):
    print(500000004)
  exit()
mod = 10**9+7
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
def inv(a):
  return pow(a,mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*inv(fctr[n-k])*inv(fctr[k])%mod

ans = [500000004]*b
nume = pow(2,b-1,mod)
domi = pow(2,b,mod)
for i in range(b+1,b+w+1):
  domi = domi*2%mod
  nume = nume*2-cmb(i-2,i-b-1)
  if i >= w:
    nume += cmb(i-2,i-w-1)
  nume %= mod
  x = nume*inv(domi)%mod
  if flg:
    ans.append(mod+1-x)
  else:
    ans.append(x)
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
def main():

  U = 2*10**5
  MOD = 10**9+7

  fact = [1]*(U+1)
  fact_inv = [1]*(U+1)
  two = [1]*(U+1)
  two_inv = [1]*(U+1)

  for i in range(1,U+1):
      fact[i] = (fact[i-1]*i)%MOD
      two[i] = (two[i-1]*2)%MOD
  fact_inv[U] = pow(fact[U], MOD-2, MOD)
  two_inv[U] = pow(two[U], MOD-2, MOD)

  for i in range(U,0,-1):
      fact_inv[i-1] = (fact_inv[i]*i)%MOD
      two_inv[i-1] = (two_inv[i]*2)%MOD

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

  B, W = map(int, input().split())
  p = 0
  q = 0
  for i in range(1, B+W+1):
    ans = 1 - p + q
    ans %= MOD
    ans *= two_inv[1]
    ans %= MOD
    print(ans)
    p += comb(i-1, B-1) * two_inv[i] % MOD
    p %= MOD
    q += comb(i-1, W-1) * two_inv[i] % MOD
    q %= MOD
    
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
two = [1]*(U+1)
two_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
    two[i] = (two[i-1]*2)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
two_inv[U] = pow(two[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
    two_inv[i-1] = (two_inv[i]*2)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
B, W = map(int, input().split())
p = 0
q = 0
for i in range(1, B+W+1):
  ans = 1 - p + q
  ans %= MOD
  ans *= two_inv[1]
  ans %= MOD
  print(ans)
  p += comb(i-1, B-1) * two_inv[i] % MOD
  p %= MOD
  q += comb(i-1, W-1) * two_inv[i] % MOD
  q %= MOD

Submission status: Accepted

Solution code:
U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
B, W = map(int, input().split())
p = 0
q = 0
for i in range(1, B+W+1):
  ans = 1 - p + q
  ans %= MOD
  ans *= pow(2, MOD-2, MOD)
  ans %= MOD
  print(ans)
  p += comb(i-1, B-1) * pow(pow(2, i, MOD), MOD-2, MOD) % MOD
  p %= MOD
  q += comb(i-1, W-1) * pow(pow(2, i, MOD), MOD-2, MOD) % MOD
  q %= MOD

Submission status: Accepted

Solution code:
b,w=map(int,input().split())
MOD=10**9+7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
factorial=[ModInt(1)]*(b+w+1)
for i in range(1,b+w+1):
    factorial[i]=factorial[i-1]*i
power_of_two=ModInt(1)
def comb(count, BorW):
    if count < BorW:return 0
    return factorial[count]/factorial[BorW]/factorial[count-BorW]
Black_doesnt_exist=[0]*(w+1)
White_doesnt_exist=[0]*(b+1)
Black_doesnt_exist[0]=ModInt(1)
White_doesnt_exist[0]=ModInt(1)
for i in range(b):
    Black_doesnt_exist[0]*=2
for i in range(w):
    White_doesnt_exist[0]*=2
Black_doesnt_exist[0]-=1;White_doesnt_exist[0]-=1
#Blackdoesn'texist[i]:=b+i個から0~b-1個を選ぶ選び方の総数
for i in range(1,w+1):
    Black_doesnt_exist[i]=Black_doesnt_exist[i-1]*2-comb(b+i-1,b-1)
for i in range(1,b+1):
    White_doesnt_exist[i]=White_doesnt_exist[i-1]*2-comb(w+i-1,w-1)
for i in range(b+w):
    B=0;W=0
    #B:前回までに黒いチョコを食べきっているような選び方
    #W:前回までに白いチョコを食べきっているような選び方
    if i>=b:
        B=power_of_two-Black_doesnt_exist[i-b]
    if i>=w:
        W=power_of_two-White_doesnt_exist[i-w]
    Both_exist=power_of_two-B-W
    print(W/power_of_two+Both_exist/power_of_two/2)
    power_of_two*=2

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_e

黒か白かを同じ確率で選ぶので、どちらも絶対無くなってないなら1/2
すなわち、 1<=i<=min(B,W) では必ず1/2を出せば終わり

それ以降は、白が存在していないなら1、黒が存在していないなら0、それ以外は1/2
よって、白が空になってる確率と黒が存在していない確率を出せばよい

白が存在していない確率は、Σj番目で白が空になる確率のように累積で求める
黒も同様
それ以外は余事象
"""

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)
    return fac[n] * inv[n-r] * inv[r] % mod


B,W = map(int,input().split())
mod = 10**9+7
fac,inv = modfac(B+W+10,mod)

half = 500000004

bzero = 0
wzero = 0

for i in range(1,B+W+1):

    print ((wzero + (1-bzero-wzero) * half) % mod)

    if i >= B:
        bzero += pow(half,i,mod) * modnCr(i-1,B-1,mod,fac,inv)
        bzero %= mod
    if i >= W:
        wzero += pow(half,i,mod) * modnCr(i-1,W-1,mod,fac,inv)
        wzero %= mod

Submission status: Accepted

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

mod = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%mod
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], mod -2, mod)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % mod
    return frac, fraci
frac, fraci = frac(1341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod

B, W = map(int, readline().split())
half = pow(2, mod-2, mod)
  
Kb = [pow(half, W+B-i+1, mod)*comb(B+W-i-1, W-1) for i in range(1, B+1)]
Kw = [pow(half, B+W-i+1, mod)*comb(B+W-i-1, B-1) for i in range(1, W+1)]


for i in range(B-2, -1, -1):
    Kb[i] = (Kb[i] + Kb[i+1])%mod
for i in range(W-2, -1, -1):
    Kw[i] = (Kw[i] + Kw[i+1])%mod

ans = [half]*(B+W)
for i in range(B):
    ans[i] = (ans[i]+Kb[i])%mod
for i in range(W):
    ans[i] = (ans[i]-Kw[i])%mod
print('\n'.join(map(str, ans[::-1])))

Submission status: Accepted

Solution code:
# D より思い付きやすい気がする

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
        if n == k: return 1  # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
        # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  # n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod))
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod

def main():
    comb = Combination(2*10**5)
    mod = 10**9+7
    B, W = map(int, input().split())

    L = [0] * (B+W+1)
    for i in range(B, B+W):
        L[i+1] = -comb(i, B)
    for i in range(W, W+B):
        L[i+1] = (L[i+1] + comb(i, W)) % mod

    L_cum = [0] + L[:-1]
    for i in range(1, B+W+1):
        L_cum[i] = (L_cum[i] + 2 * L_cum[i-1]) % mod

    Ans = []
    p = 1
    half = pow(2, mod-2, mod)
    denom_inv = half
    for l, l_cum in zip(L[1:], L_cum[1:]):
        Ans.append((p+l+l_cum) * denom_inv % mod)
        p = p * 2 % mod
        denom_inv = denom_inv * half % mod
    print("\n".join(map(str, Ans)))

main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

MOD = 10 ** 9 + 7

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

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

U = 2*10**5 + 100
x = np.arange(U,dtype=np.int64); x[0] = 1
fact = cumprod(x)
x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod(x)[::-1]

x = np.full(U,pow(2,MOD-2,MOD),dtype=np.int64); x[0] = 1
pow2_inv = cumprod(x)

# 各時点で、単色になっている確率
black_only = np.zeros(B+W,np.int64)
x = fact[W-1:B+W-1] % MOD * fact_inv[0:B] % MOD * fact_inv[W-1] % MOD
black_only[W:B+W] = pow2_inv[W:B+W] * x % MOD
np.cumsum(black_only,out=black_only)
black_only %= MOD

white_only = np.zeros(W+B,np.int64)
x = fact[B-1:W+B-1] % MOD * fact_inv[0:W] % MOD * fact_inv[B-1] % MOD
white_only[B:W+B] = pow2_inv[B:W+B] * x % MOD
np.cumsum(white_only,out=white_only)
white_only %= MOD

answer = (1+black_only-white_only) * pow(2,MOD-2,MOD) % MOD
print('\n'.join(answer.astype(str)))