Strange Operation (Codeforces 1383E)
Tags: DP, combinatorics

Koa the Koala has a binary string $$$s$$$ of length $$$n$$$. Koa can perform no more than $$$n-1$$$ (possibly zero) operations of the following form:In one operation Koa selects positions $$$i$$$ and $$$i+1$$$ for some $$$i$$$ with $$$1 \le i < |s|$$$ and sets $$$s_i$$$ to $$$max(s_i, s_{i+1})$$$. Then Koa deletes position $$$i+1$$$ from $$$s$$$ (after the removal, the remaining parts are concatenated).Note that after every operation the length of $$$s$$$ decreases by $$$1$$$.How many different binary strings can Koa obtain by doing no more than $$$n-1$$$ (possibly zero) operations modulo $$$10^9+7$$$ ($$$1000000007$$$)?

Input: The only line of input contains binary string $$$s$$$ ($$$1 \le |s| \le 10^6$$$). For all $$$i$$$ ($$$1 \le i \le |s|$$$) $$$s_i = 0$$$ or $$$s_i = 1$$$.

Output: On a single line print the answer to the problem modulo $$$10^9+7$$$ ($$$1000000007$$$).

Note: In the first sample Koa can obtain binary strings: $$$0$$$, $$$00$$$ and $$$000$$$.In the second sample Koa can obtain binary strings: $$$1$$$, $$$01$$$, $$$11$$$, $$$011$$$, $$$101$$$ and $$$0101$$$. For example:  to obtain $$$01$$$ from $$$0101$$$ Koa can operate as follows: $$$0101 \rightarrow 0(10)1 \rightarrow 011 \rightarrow 0(11) \rightarrow 01$$$.  to obtain $$$11$$$ from $$$0101$$$ Koa can operate as follows: $$$0101 \rightarrow (01)01 \rightarrow 101 \rightarrow 1(01) \rightarrow 11$$$. Parentheses denote the two positions Koa selected in each operation.

Sample Inputs:
000

0101

0001111

00101100011100

Sample Outputs:
3

6

16

477

Solution (Python):
MOD = 1000000007

def main():
    s = input()
    n = len(s)
    zero = [0] * n
    for i in range(n):
        if s[i] == '0':
            zero[i] = zero[i - 1] + 1 if i else 1
    (nxt, dp) = ([0] * (n + 2), [0] * (n + 2))
    for i in range(n + 1):
        nxt[i] = n
    for i in range(n - 1, -1, -1):
        dp[i] = ((zero[i] <= zero[n - 1]) + dp[nxt[0]] + dp[nxt[zero[i] + 1]]) % MOD
        nxt[zero[i]] = i
    ans = n if nxt[0] >= n else dp[nxt[0]] * (nxt[0] + 1) % MOD
    print(ans)
main()

Solution (Python):
import sys
MOD = 1000000007

def red(x):
    return x if x < MOD else x - MOD
S = input()
n = len(S)
i = 0
while i < n and S[i] == '0':
    i += 1
if i == n:
    print(n)
    sys.exit()
j = n
while j and S[j - 1] == '0':
    j -= 1
fac = (i + 1) * (n - j + 1)
S = S[i:j]
n = len(S)
count0 = [+(c == '0') for c in S]
for i in reversed(range(n - 1)):
    if count0[i]:
        count0[i] += count0[i + 1]
ways0 = 1
ways1 = 0
buckets = [0] * (n + 1)
buckets[0] = 1
for i in reversed(range(n)):
    if count0[i]:
        c = count0[i]
        ways0 = red(ways0 - buckets[c] + MOD)
        buckets[c] = ways1
        ways0 = red(ways0 + ways1)
    else:
        ways1 = red(ways1 + ways0)
print(ways1 * fac % MOD)

Solution (Python):
import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
S = readline().strip().split('1')
if len(S) == 1:
    print(len(S[0]))
else:
    S = [len(s) + 1 for s in S]
    ans = S[0] * S[-1]
    S = S[1:-1]
    dp = [0] * (max(S) + 2)
    dp[0] = 1
    for ai in S:
        res = 0
        rz = 0
        for i in range(ai + 1):
            res = (res + dp[i]) % MOD
            rz = (rz + (ai - i) * dp[i]) % MOD
            dp[i] = 0
        dp[0] = rz
        dp[ai] = res
    aaa = 0
    for d in dp:
        aaa = (aaa + d) % MOD
    print(aaa * ans % MOD)