Placing Jinas (Codeforces 1696E)
Tags: Math, combinatorics

We say an infinite sequence $$$a_{0}, a_{1}, a_2, \ldots$$$ is non-increasing if and only if for all $$$i\ge 0$$$, $$$a_i \ge a_{i+1}$$$.There is an infinite right and down grid. The upper-left cell has coordinates $$$(0,0)$$$. Rows are numbered $$$0$$$ to infinity from top to bottom, columns are numbered from $$$0$$$ to infinity from left to right.There is also a non-increasing infinite sequence $$$a_{0}, a_{1}, a_2, \ldots$$$. You are given $$$a_0$$$, $$$a_1$$$, $$$\ldots$$$, $$$a_n$$$; for all $$$i>n$$$, $$$a_i=0$$$. For every pair of $$$x$$$, $$$y$$$, the cell with coordinates $$$(x,y)$$$ (which is located at the intersection of $$$x$$$-th row and $$$y$$$-th column) is white if $$$y<a_x$$$ and black otherwise.Initially there is one doll named Jina on $$$(0,0)$$$. You can do the following operation.  Select one doll on $$$(x,y)$$$. Remove it and place a doll on $$$(x,y+1)$$$ and place a doll on $$$(x+1,y)$$$. Note that multiple dolls can be present at a cell at the same time; in one operation, you remove only one. Your goal is to make all white cells contain $$$0$$$ dolls.What's the minimum number of operations needed to achieve the goal? Print the answer modulo $$$10^9+7$$$.

Input: The first line of input contains one integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$).The second line of input contains $$$n+1$$$ integers $$$a_0,a_1,\ldots,a_n$$$ ($$$0\le a_i\le 2\cdot 10^5$$$).It is guaranteed that the sequence $$$a$$$ is non-increasing.

Output: Print one integer — the answer to the problem, modulo $$$10^9+7$$$.

Note: Consider the first example. In the given grid, cells $$$(0,0),(0,1),(1,0),(1,1)$$$ are white, and all other cells are black. Let us use triples to describe the grid: triple $$$(x,y,z)$$$ means that there are $$$z$$$ dolls placed on cell $$$(x,y)$$$. Initially the state of the grid is $$$(0,0,1)$$$.One of the optimal sequence of operations is as follows:  Do the operation with $$$(0,0)$$$. Now the state of the grid is $$$(1,0,1),(0,1,1)$$$.  Do the operation with $$$(0,1)$$$. Now the state of the grid is $$$(1,0,1),(1,1,1),(0,2,1)$$$.  Do the operation with $$$(1,0)$$$. Now the state of the grid is $$$(1,1,2),(0,2,1),(2,0,1)$$$.  Do the operation with $$$(1,1)$$$. Now the state of the grid is $$$(1,1,1),(0,2,1),(2,0,1),(1,2,1),(2,1,1)$$$.  Do the operation with $$$(1,1)$$$. Now the state of the grid is $$$(0,2,1),(2,0,1),(1,2,2),(2,1,2)$$$. Now all white cells contain $$$0$$$ dolls, so we have achieved the goal with $$$5$$$ operations.

Sample Inputs:
2
2 2 0

10
12 11 8 8 6 6 6 5 3 2 1

Sample Outputs:
5

2596

Solution (Python):
mod = 10 ** 9 + 7
m = 4 * 10 ** 5 + 1
f = [None] * m
f[0] = 1
for i in range(1, m):
    f[i] = f[i - 1] * i % mod
f_inv = [None] * m
f_inv[-1] = pow(f[-1], mod - 2, mod)
for i in reversed(range(1, m)):
    f_inv[i - 1] = f_inv[i] * i % mod
input()
print(sum((f[a + i] * f_inv[a - 1] * f_inv[i + 1] for (i, a) in enumerate(map(int, input().split())) if a > 0)) % mod)

Solution (Python):
import sys

def solve():
    F = [None] * int(400000.0 + 4)
    Finv = [None] * len(F)
    F[0] = 1
    MOD = int(1000000000.0 + 7)
    for i in range(1, len(F)):
        F[i] = F[i - 1] * i % MOD
    Finv[-1] = pow(F[-1], MOD - 2, MOD)
    for i in range(len(F) - 1, 0, -1):
        Finv[i - 1] = Finv[i] * i % MOD
    inp = sys.stdin.readline
    n = int(inp())
    a = list(map(int, inp().split()))
    r = 0
    for i in range(n + 1):
        if a[i] > 0:
            r = (r + F[a[i] + i] * Finv[a[i] - 1] * Finv[i + 1]) % MOD
    print(r)

def main():
    solve()
if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10 ** 9 + 7
ans = 0
fact = [1]
for i in range(1, 4 * 10 ** 5 + 5):
    fact.append(fact[-1] * i % MOD)

def c(m, n):
    return fact[m] * pow(fact[m - n] * fact[n], -1, MOD)
n = int(input())
for (i, a) in enumerate(map(int, input().split())):
    if a > 0:
        ans += c(a + i, i + 1) % MOD
        ans %= MOD
print(ans)