AtCoder Regular Contest 065 - Shuffling

There is a string S of length N consisting of characters 0 and 1. You will perform the following operation for each i = 1, 2, ..., m:
 - Arbitrarily permute the characters within the substring of S starting at the l_i-th character from the left and extending through the r_i-th character.
Here, the sequence l_i is non-decreasing.
How many values are possible for S after the M operations, modulo 1000000007(= 10^9+7)?

-----Constraints-----
 - 2≦N≦3000
 - 1≦M≦3000
 - S consists of characters 0 and 1.
 - The length of S equals N.
 - 1≦l_i < r_i≦N
 - l_i ≦ l_{i+1}

-----Input-----
The input is given from Standard Input in the following format:
N M
S
l_1 r_1
:
l_M r_M

-----Output-----
Print the number of the possible values for S after the M operations, modulo 1000000007.

-----Sample Input-----
5 2
01001
2 4
3 5

-----Sample Output-----
6

After the first operation, S can be one of the following three: 01001, 00101 and 00011.
After the second operation, S can be one of the following six: 01100, 01010, 01001, 00011, 00101 and 00110.

Source: atcoder | Difficulty: VERY_HARD


Solutions:
M = 10 ** 9 + 7

def solve(n, m, s, lst):
	cnt = [0] * n
	t = 0
	for i in range(n):
		if s[i] == '1':
			t += 1
		cnt[i] = t
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	dp[0][0] = 1
	r = 0
	j = 0
	for i in range(n):
		while j < m:
			(lj, rj) = lst[j]
			if lj <= i:
				r = max(r, rj)
				j += 1
			else:
				break
		if r <= i:
			c = cnt[i]
			if 0 < c:
				dp[i + 1][cnt[i]] = (dp[i][c] + dp[i][c - 1]) % M
			else:
				dp[i + 1][0] = dp[i][0]
		else:
			for k in range(max(0, cnt[r] - r + i), min(i + 1, cnt[r]) + 1):
				if 0 < k:
					dp[i + 1][k] = (dp[i][k] + dp[i][k - 1]) % M
				else:
					dp[i + 1][0] = dp[i][0]
	return dp[n][cnt[n - 1]]

def main():
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	s = input()
	lst = []
	for _ in range(m):
		(l, r) = input().split()
		l = int(l) - 1
		r = int(r) - 1
		lst.append((l, r))
	print(solve(n, m, s, lst))

def __starting_point():
	main()
__starting_point()


mod = 10 ** 9 + 7
(N, M) = map(int, input().split())
L = -1
R = -1
S = input()
ope = []
for i in range(M):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	if L <= l and r <= R:
		continue
	else:
		(L, R) = (l, r)
		ope.append((l, r))
M = len(ope)
data = [-1] * N
for i in range(M):
	(l, r) = ope[i]
	for j in range(l, r + 1):
		data[j] = i
dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
for j in range(N + 1):
	dp[-1][j] = 1
for i in range(N - 1, -1, -1):
	id = data[i]
	if id != -1:
		(l, r) = ope[id]
		temp1 = sum((int(S[k]) for k in range(r + 1)))
		temp0 = r + 1 - temp1
		for j in range(temp1 + 1):
			np1 = temp1 - j
			np0 = temp0 - (i - j)
			if np1 == 0:
				if np0 > 0:
					dp[i][j] = dp[i + 1][j]
			elif np0 > 0:
				dp[i][j] = (dp[i + 1][j + 1] + dp[i + 1][j]) % mod
			elif np0 == 0:
				dp[i][j] = dp[i + 1][j + 1]
	elif S[i] == '1':
		for j in range(N):
			dp[i][j] = dp[i + 1][j + 1]
	else:
		for j in range(N + 1):
			dp[i][j] = dp[i + 1][j]
print(dp[0][0])


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n, m) = map(int, readline().split())
s = input()
mp = map(int, read().split())
r = list(range(n))
for (i, j) in zip(mp, mp):
	if r[i - 1] < j - 1:
		r[i - 1] = j - 1
for i in range(1, n):
	if r[i] < r[i - 1]:
		r[i] = r[i - 1]
zero = [0] * n
one = [0] * n
for i in range(n):
	zero[i] = zero[i - 1]
	one[i] = one[i - 1]
	if s[i] == '0':
		zero[i] += 1
	else:
		one[i] += 1
MOD = 10 ** 9 + 7
dp = [0] * n
dp[0] = 1
for i in range(n):
	L = max(zero[r[i]] + i - r[i], 0)
	R = min(zero[r[i]], i + 1)
	ndp = [0] * n
	for i in range(L, R + 1):
		if i:
			ndp[i] += dp[i - 1]
		ndp[i] += dp[i]
		ndp[i] %= MOD
	dp = ndp
print(sum(dp))


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
(N, M) = list(map(int, readline().split()))
S = list(map(int, readline().strip()))
Query = [tuple([int(x) - 1 for x in readline().split()]) for _ in range(M)]
PP = S.count(1)
Li = [None] * PP
Ri = [None] * PP
T1 = S[:]
for (l, r) in Query:
	cnt = 0
	for i in range(l, r + 1):
		cnt += T1[i]
	for i in range(l, l + cnt):
		T1[i] = 1
	for i in range(l + cnt, r + 1):
		T1[i] = 0
T2 = S[:]
for (l, r) in Query:
	cnt = 0
	for i in range(l, r + 1):
		cnt += 1 - T2[i]
	for i in range(l, l + cnt):
		T2[i] = 0
	for i in range(l + cnt, r + 1):
		T2[i] = 1
cnt = 0
for i in range(N):
	if T1[i]:
		Li[cnt] = i
		cnt += 1
cnt = 0
for i in range(N):
	if T2[i]:
		Ri[cnt] = i + 1
		cnt += 1
dp = [0] * N
for i in range(Li[0], Ri[0]):
	dp[i] = 1
for j in range(1, PP):
	dp2 = [0] + dp[:-1]
	for i in range(1, N):
		dp2[i] = (dp2[i] + dp2[i - 1]) % MOD
	for i in range(Li[j]):
		dp2[i] = 0
	for i in range(Ri[j], N):
		dp2[i] = 0
	dp = dp2[:]
res = 0
for d in dp:
	res = (res + d) % MOD
print(res)


from collections import deque
import heapq
(N, M) = map(int, input().split())
S = input()
lri = []
for i in range(M):
	(l, r) = map(int, input().split())
	lri.append([l - 1, r - 1, i])
lri.append([N, float('inf'), float('inf')])
nexvisit = 0
onenum = 0
LRlis = []
LRlisind = 0
r = 0
for loop in range(M):
	(l, nr, tempi) = lri[loop]
	r = max(nr, r)
	nexl = lri[loop + 1][0]
	for i in range(max(l, nexvisit), r + 1):
		if S[i] == '1':
			LRlis.append([l, None])
			onenum += 1
			nexvisit = max(nexvisit, i + 1)
	if r - nexl + 1 < onenum:
		for i in range(min(onenum, onenum - (r - nexl + 1))):
			LRlis[LRlisind][1] = r - onenum + 1
			onenum -= 1
			LRlisind += 1
mod = 10 ** 9 + 7
dp = [0] * (N + 1)
for i in range(len(LRlis)):
	(l, r) = LRlis[i]
	ndp = [0] * (N + 1)
	if i == 0:
		ndp[l] += 1
		ndp[r + 1] -= 1
	else:
		for v in range(r):
			ndp[max(l, v + 1)] += dp[v]
			ndp[r + 1] -= dp[v]
	for j in range(N):
		ndp[j + 1] += ndp[j]
		ndp[j] %= mod
		ndp[j + 1] % mod
	dp = ndp
print(sum(dp[0:N]) % mod)


import sys
input = sys.stdin.readline
import numpy as np
MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
S = np.array(list(input().rstrip()), dtype='U1')
LR = [[int(x) for x in input().split()] for _ in range(M)]
cnt_0 = (S == '0').cumsum()
cnt_1 = (S == '1').cumsum()
canuse_0 = cnt_0
canuse_1 = cnt_1
for (L, R) in LR:
	canuse_0[L - 1] = max(canuse_0[L - 1], cnt_0[R - 1])
	canuse_1[L - 1] = max(canuse_1[L - 1], cnt_1[R - 1])
np.maximum.accumulate(canuse_0, out=canuse_0)
np.maximum.accumulate(canuse_1, out=canuse_1)
dp = np.zeros(N + 1, dtype=np.int64)
dp[0] = 1
for i in range(N):
	prev = dp
	dp = np.zeros(N + 1, dtype=np.int64)
	left = max(0, i + 1 - canuse_0[i])
	right = canuse_1[i]
	dp[left:right + 1] += prev[left:right + 1]
	left = max(1, left)
	dp[left:right + 1] += prev[left - 1:right]
	dp %= MOD
answer = dp.sum()
print(answer)