AtCoder Regular Contest 074 - RGB Sequence

There are N squares arranged in a row.
The squares are numbered 1, 2, ..., N, from left to right.
Snuke is painting each square in red, green or blue.
According to his aesthetic sense, the following M conditions must all be satisfied.
The i-th condition is:
 - There are exactly x_i different colors among squares l_i, l_i + 1, ..., r_i.
In how many ways can the squares be painted to satisfy all the conditions?
Find the count modulo 10^9+7.

-----Constraints-----
 - 1 ≤ N ≤ 300
 - 1 ≤ M ≤ 300
 - 1 ≤ l_i ≤ r_i ≤ N
 - 1 ≤ x_i ≤ 3

-----Input-----
Input is given from Standard Input in the following format:
N M
l_1 r_1 x_1
l_2 r_2 x_2
:
l_M r_M x_M

-----Output-----
Print the number of ways to paint the squares to satisfy all the conditions, modulo 10^9+7.

-----Sample Input-----
3 1
1 3 3

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

The six ways are:
 - RGB
 - RBG
 - GRB
 - GBR
 - BRG
 - BGR
where R, G and B correspond to red, green and blue squares, respectively.

Source: atcoder | Difficulty: VERY_HARD


Solutions:
(N, M) = map(int, input().split())
q = [[] for i in range(N + 1)]
for i in range(M):
	(l, r, x) = map(int, input().split())
	q[r].append((l, x))
mod = 10 ** 9 + 7
dp = [[0 for i in range(N + 1)] for i in range(N + 1)]
i = N
for j in range(N + 1):
	for k in range(N + 1):
		check = 7
		for (l, x) in q[i]:
			if i == l:
				check = (x == 1) * check
			elif i - 1 >= l > j:
				check = (x == 1) * (check % 2) + (x == 2) * (check & 6)
			elif j >= l > k:
				check = (x == 2) * (check & 3) + (x == 3) * (check & 4)
			else:
				check *= x == 3
		dp[j][k] = bin(check).count('1')
ndp = [[0 for j in range(N + 1)] for k in range(N + 1)]
for i in range(N - 1, 0, -1):
	for j in range(i):
		for k in range(j + 1):
			check = 7
			for (l, x) in q[i]:
				if i == l:
					check = (x == 1) * check
				elif i - 1 >= l > j:
					check = (x == 1) * (check % 2) + (x == 2) * (check & 6)
				elif j >= l > k:
					check = (x == 2) * (check & 3) + (x == 3) * (check & 4)
				else:
					check *= x == 3
			ndp[j][k] = (dp[j][k] * (check // 1 % 2) + dp[i - 1][k] * (check // 2 % 2) + dp[i - 1][j] * (check // 4 % 2)) % mod
	dp = ndp
print(dp[0][0])


MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
S = [[N] * (N + 1) for i in [0, 1, 2]]
T = [[0] * (N + 1) for i in [0, 1, 2]]
C = [0] * (N + 1)
for i in range(M):
	(l, r, x) = map(int, input().split())
	S[x - 1][r] = min(S[x - 1][r], l)
	T[x - 1][r] = max(T[x - 1][r], l)
	C[r] = 1
(S0, S1, S2) = S
(T0, T1, T2) = T
ok = 1
for i in range(N + 1):
	if not T2[i] < S1[i] or not T1[i] < S0[i]:
		ok = 0
		break
if not ok:
	print(0)
	exit(0)
X = {(0, 0): 3}
for b in range(1, N):
	t2 = T2[b + 1]
	s1 = S1[b + 1]
	t1 = T1[b + 1]
	s0 = S0[b + 1]
	check = lambda r, g: t2 <= r < s1 and t1 <= g < s0
	Z = [0] * (N + 1)
	if C[b + 1]:
		if t1 <= b < s0:
			for ((r, g), v) in X.items():
				if t2 <= g < s1:
					Z[g] += v
				if t2 <= r < s1:
					Z[r] += v
		X = {(r, g): v for ((r, g), v) in X.items() if t2 <= r < s1 and t1 <= g < s0}
	else:
		Z = [0] * (N + 1)
		for ((r, g), v) in X.items():
			Z[g] += v
			Z[r] += v
	for (z, v) in enumerate(Z):
		if v:
			X[z, b] = v % MOD
print(sum(X.values()) % MOD)


from collections import defaultdict
MOD = 1000000007
iist = lambda : map(int, input().split())
(N, M) = iist()
Q = defaultdict(list)
for i in range(M):
	(l, r, x) = iist()
	Q[r].append((l, x))
if any((x != 1 for (l, x) in Q[1])):
	print(0)
	return
dp = defaultdict(int)
dp[0, 0] = 3
x_sum = [3]
y_sum = [3]
s = 3
for pk in range(1, N):
	k = pk + 1
	for (i, (a, b)) in enumerate(zip(x_sum, y_sum)):
		c = (a + b) % MOD
		dp[i, pk] = c
		x_sum[i] += c
	x_sum.append(0)
	y_sum.append(2 * s % MOD)
	s *= 3
	subQ = Q[k]
	for (i, j) in list(dp.keys()):
		for (l, x) in subQ:
			if x != (l <= i) + (l <= j) + 1:
				c = dp[i, j]
				x_sum[i] -= c
				y_sum[j] -= c
				s -= c
				del dp[i, j]
				break
	for i in range(pk):
		x_sum[i] %= MOD
		y_sum[i] %= MOD
	s %= MOD
print(s)


import sys
readline = sys.stdin.readline

def viol(c2, c3, l, x):
	res = False
	if x == 1:
		if not c2 < l:
			res = True
	elif x == 2:
		if not c3 < l <= c2:
			res = True
	elif not l <= c3:
		res = True
	return res
MOD = 10 ** 9 + 7
(N, M) = map(int, readline().split())
limit = [[] for _ in range(N + 3)]
for _ in range(M):
	(l, r, x) = map(int, readline().split())
	limit[r + 2].append((l + 2, x))
dp = [[0, 0], [1, 0]]
for i in range(2, N + 2):
	dp2 = [[0] * (i + 1) for _ in range(i + 1)]
	r = i
	for g in range(r):
		for b in range(g):
			d = dp[g][b]
			dp2[g][b] = (dp2[g][b] + d) % MOD
			dp2[r][b] = (dp2[r][b] + d) % MOD
			dp2[r][g] = (dp2[r][g] + d) % MOD
	for (l, x) in limit[i + 1]:
		r = i + 1
		for g in range(r):
			for b in range(g):
				if viol(g, b, l, x):
					dp2[g][b] = 0
	dp = [d[:] for d in dp2]
res = 0
for g in range(N + 2):
	for b in range(g):
		res = (res + dp[g][b]) % MOD
print(res)


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7

def check(i, j, l, x):
	return x == 3 and l <= i or (x == 2 and i < l <= j) or (x == 1 and j < l)
(N, M) = map(int, input().split())
LRX = [list(map(int, input().split())) for _ in range(M)]
LX = [[] for _ in range(N + 2)]
for (l, r, x) in LRX:
	LX[r].append((l, x))
dp = [[[0] * (j + 1) for j in range(i + 1)] for i in range(N + 2)]
dp[0][0][0] = 1
for i in range(N + 1):
	for j in range(i, N + 1):
		for k in range(j, N + 1):
			ok = True
			for (l, x) in LX[k + 1]:
				if not check(j, k, l, x):
					ok = False
					break
			if ok:
				dp[k + 1][k][j] = (dp[k + 1][k][j] + dp[k][j][i]) % mod
			ok = True
			for (l, x) in LX[k + 1]:
				if not check(i, j, l, x):
					ok = False
					break
			if ok:
				dp[k + 1][j][i] = (dp[k + 1][j][i] + dp[k][j][i]) % mod
			ok = True
			for (l, x) in LX[k + 1]:
				if not check(i, k, l, x):
					ok = False
					break
			if ok:
				dp[k + 1][k][i] = (dp[k + 1][k][i] + dp[k][j][i]) % mod
ans = 0
for a in range(N + 1):
	for b in range(a, N + 1):
		ans = (ans + dp[N][b][a]) % mod
print(ans)


MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
S = [[N + 1] * (N + 1) for i in [0, 1, 2]]
T = [[0] * (N + 1) for i in [0, 1, 2]]
C = [0] * (N + 1)
for i in range(M):
	(l, r, x) = map(int, input().split())
	if r - l < x - 1:
		print(0)
		exit(0)
	S[x - 1][r] = min(S[x - 1][r], l)
	T[x - 1][r] = max(T[x - 1][r], l)
	C[r] = 1
(S0, S1, S2) = S
(T0, T1, T2) = T
ok = 1
for i in range(N + 1):
	if not T2[i] < S1[i] or not T1[i] < S0[i]:
		ok = 0
		break
if not ok:
	print(0)
	exit(0)
RM = [N + 1] * (N + 1)
GM = [N + 1] * (N + 1)
for i in range(N - 1, -1, -1):
	RM[i] = min(RM[i + 1], S1[i + 1])
	GM[i] = min(GM[i + 1], S0[i + 1])
X = {(0, 0): 3}
D = [0] * (N + 1)
D[0] = 6
B = [{} for i in range(N + 1)]
B[0][0] = 3
bb = 0
for b in range(1, N):
	t2 = T2[b + 1]
	s1 = S1[b + 1]
	t1 = T1[b + 1]
	s0 = S0[b + 1]
	rm = RM[b]
	gm = GM[b]
	if t1 <= b < gm:
		F = B[b]
		for z in range(t2, min(rm, b)):
			v = D[z] % MOD
			if v:
				F[z] = v
				D[z] += v
				D[b] += v
	if C[b + 1]:
		for g in range(bb, min(t1, b)):
			for (r, v) in B[g].items():
				D[r] -= v
				D[g] -= v
			B[g] = None
		bb = max(t1, bb)
		for g in range(bb, b):
			for (r, v) in B[g].items():
				if not t2 <= r < s1:
					D[r] -= v
					D[g] -= v
			B[g] = {r: v for (r, v) in B[g].items() if t2 <= r < s1}
ans = 0
for b in range(bb, N + 1):
	if B[b]:
		ans += sum(B[b].values())
print(ans % MOD)


from collections import defaultdict
MOD = 1000000007
iist = lambda : map(int, input().split())
(N, M) = iist()
Q = defaultdict(list)
for i in range(M):
	(l, r, x) = iist()
	Q[r].append((l, x - 1))
if any((x != 0 for (l, x) in Q[1])):
	print(0)
	exit(0)
dp = {(0, 0): 3}
memo = [6]
s = 3
for pk in range(1, N):
	k = pk + 1
	for (i, c) in enumerate(memo):
		c %= MOD
		dp[i, pk] = c
		memo[i] *= 2
		memo[i] %= MOD
	memo.append(2 * s % MOD)
	s = 3 * s % MOD
	subQ = Q[k]
	for (i, j) in list(dp.keys()):
		for (l, x) in subQ:
			if x != (l <= i) + (l <= j):
				c = dp[i, j]
				memo[i] -= c
				memo[j] -= c
				s -= c
				del dp[i, j]
				break
	s %= MOD
print(s)


(N, M) = map(int, input().split())
Q = [[int(i) for i in input().split()] for i in range(M)]
Q.sort(key=lambda x: x[1])
mod = 10 ** 9 + 7
dp = [[[0] * max(1, c) for c in range(max(1, b + 1))] for b in range(N + 1)]
dp[0][0][0] = 1
k = 0
for a in range(N + 1):
	check = []
	if k <= M - 1:
		while a == Q[k][1]:
			(l, r, x) = Q[k]
			check.append((l, r, x))
			k += 1
			if k == M:
				break
	for b in range(max(1, a)):
		for c in range(max(1, b)):
			for (l, r, x) in check:
				if x == 1:
					if not b < l:
						dp[a][b][c] = 0
						continue
				elif x == 2:
					if not (b >= l and c < l):
						dp[a][b][c] = 0
						continue
				elif x == 3:
					if not c >= l:
						dp[a][b][c] = 0
						continue
			dp[a][b][c] %= mod
			if a <= N - 1:
				dp[a + 1][b][c] += dp[a][b][c]
				dp[a + 1][a][c] += dp[a][b][c]
				dp[a + 1][a][b] += dp[a][b][c]
ans = 0
for b in range(N):
	for c in range(max(1, b)):
		ans += dp[N][b][c]
		ans %= mod
print(ans)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n, m) = map(int, readline().split())
cond = [[] for _ in range(n + 1)]
for _ in range(m):
	(l, r, x) = map(int, readline().split())
	cond[r].append((l, x))
N = n + 3
dp = [[0] * N for _ in range(N)]
dp[1][2] = 1
MOD = 10 ** 9 + 7

def f(r, j, k, v, ndp):
	if j >= N or k >= N:
		return
	for (l, x) in cond[r]:
		if x == 1 and l <= r - j:
			return
		if x == 2 and (r - j < l or l <= r - k):
			return
		if x == 3 and r - k < l:
			return
	ndp[j][k] += v
	ndp[j][k] %= MOD
	return
for i in range(1, n + 1):
	ndp = [[0] * N for _ in range(N)]
	for q in range(1, N):
		for r in range(q + 1, N):
			v = dp[q][r]
			if v:
				f(i, q + 1, r + 1, v, ndp)
				f(i, 1, r + 1, v, ndp)
				f(i, 1, q + 1, v, ndp)
	dp = ndp
ans = sum((sum(i) for i in dp))
print(ans % MOD)


from itertools import permutations
(n, m) = map(int, input().split())
lrx = [list(map(int, input().split())) for i in range(m)]
lrx.sort(key=lambda x: x[1])
mod = 10 ** 9 + 7
dp = [[[0 for b in range(max(1, g))] for g in range(max(1, r))] for r in range(n + 1)]
dp[0][0][0] = 1
for (l, r, t) in lrx:
	if t != 1:
		for g in range(l):
			for b in range(max(1, g)):
				dp[r][g][b] = -1
	if t != 2:
		for g in range(l, r):
			for b in range(l):
				dp[r][g][b] = -1
	if t != 3:
		for g in range(l, r):
			for b in range(l, g):
				dp[r][g][b] = -1
for r in range(n):
	for g in range(max(1, r)):
		for b in range(max(1, g)):
			v = dp[r][g][b]
			if v == -1:
				continue
			if dp[r + 1][g][b] >= 0:
				dp[r + 1][g][b] += v
				dp[r + 1][g][b] %= mod
			if dp[r + 1][r][b] >= 0:
				dp[r + 1][r][b] += v
				dp[r + 1][r][b] %= mod
			if dp[r + 1][r][g] >= 0:
				dp[r + 1][r][g] += v
				dp[r + 1][r][g] %= mod
ans = 0
for i in range(n):
	for j in range(max(1, i)):
		if dp[n][i][j] >= 0:
			ans += dp[n][i][j]
			ans %= mod
print(ans % mod)


import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict
MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
LRX = [[int(x) for x in input().split()] for _ in range(M)]
R_to_LX = defaultdict(list)
for (l, r, x) in LRX:
	R_to_LX[r].append((l, x))
for n in range(1, N + 1):
	if n == 1:
		dp = np.zeros((n, n), dtype=np.int64)
		dp[0, 0] = 1
	else:
		prev = dp
		dp = np.zeros((n, n), dtype=np.int64)
		dp[:-1, :-1] = prev
		dp[n - 1, :-1] = prev.sum(axis=0)
		dp[:-1, n - 1] = prev.sum(axis=1)
	for (l, x) in R_to_LX[n]:
		if x == 1:
			dp[l:, :] = 0
			dp[:, l:] = 0
		elif x == 2:
			dp[l:, l:] = 0
			dp[:l, :l] = 0
		elif x == 3:
			dp[:l, :] = 0
			dp[:, :l] = 0
	dp %= MOD
answer = dp.sum() * 3 % MOD
print(answer)


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

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 main():
	md = 10 ** 9 + 7
	(n, m) = MI()
	rtol = defaultdict(list)
	for _ in range(m):
		(l, r, x) = MI()
		rtol[r].append([l, x])
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	dp[0][0] = 1
	for k in range(1, n + 1):
		for i in range(k - 1):
			dp[i][k - 1] = dp[k - 1][i] = sum(dp[i][:k - 1]) % md
		for (l, x) in rtol[k]:
			if x == 1:
				for i in range(l, k):
					for j in range(k):
						dp[i][j] = dp[j][i] = 0
			if x == 2:
				for i in range(l, k):
					for j in range(i + 1, k):
						dp[i][j] = dp[j][i] = 0
				for i in range(l):
					for j in range(i + 1):
						dp[i][j] = dp[j][i] = 0
			if x == 3:
				for i in range(l):
					for j in range(k):
						dp[i][j] = dp[j][i] = 0
	print(sum((sum(dr) for dr in dp)) * 3 % md)
main()