Runner's Problem (Codeforces 954F)
Tags: DP, matrices

You are running through a rectangular field. This field can be represented as a matrix with 3 rows and m columns. (i, j) denotes a cell belonging to i-th row and j-th column.You start in (2, 1) and have to end your path in (2, m). From the cell (i, j) you may advance to:  (i - 1, j + 1) — only if i > 1,  (i, j + 1), or  (i + 1, j + 1) — only if i < 3. However, there are n obstacles blocking your path. k-th obstacle is denoted by three integers ak, lk and rk, and it forbids entering any cell (ak, j) such that lk ≤ j ≤ rk.You have to calculate the number of different paths from (2, 1) to (2, m), and print it modulo 109 + 7.

Input: The first line contains two integers n and m (1 ≤ n ≤ 104, 3 ≤ m ≤ 1018) — the number of obstacles and the number of columns in the matrix, respectively.Then n lines follow, each containing three integers ak, lk and rk (1 ≤ ak ≤ 3, 2 ≤ lk ≤ rk ≤ m - 1) denoting an obstacle blocking every cell (ak, j) such that lk ≤ j ≤ rk. Some cells may be blocked by multiple obstacles.

Output: Print the number of different paths from (2, 1) to (2, m), taken modulo 109 + 7. If it is impossible to get from (2, 1) to (2, m), then the number of paths is 0.


Sample Inputs:
2 5
1 3 4
2 2 3

Sample Outputs:
2

Solution (Python):
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline

def _mul(A, B, MOD):
    C = [[0] * len(B[0]) for i in range(len(A))]
    for i in range(len(A)):
        for k in range(len(B)):
            for j in range(len(B[0])):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
    return C

def pow_matrix(A, n, MOD):
    B = [[0] * len(A) for i in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = _mul(A, B, MOD)
        A = _mul(A, A, MOD)
        n = n // 2
    return B

def calc(A, vec, MOD):
    n = len(vec)
    res = [0] * n
    for i in range(n):
        for j in range(n):
            res[i] += A[i][j] * vec[j]
            res[i] %= MOD
    return res
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7
res = [[] for i in range(3)]
for (row, l, r) in info:
    row -= 1
    l -= 1
    res[row].append((l, r))
for row in range(3):
    res[row].sort(key=itemgetter(1))
blocks = {}
ind_set = set([])
for row in range(3):
    tmp = []
    for (l, r) in res[row]:
        if not tmp:
            tmp.append((l, r))
            continue
        while tmp:
            if l <= tmp[-1][1]:
                (pl, pr) = tmp.pop()
                l = min(pl, l)
            else:
                break
        tmp.append((l, r))
    for (l, r) in tmp:
        if l not in blocks:
            blocks[l] = []
        if r not in blocks:
            blocks[r] = []
        blocks[l].append((row, 1))
        blocks[r].append((row, -1))
        ind_set.add(l)
        ind_set.add(r)
ind_list = sorted(list(ind_set))
dp = [0, 1, 0]
matrix = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
prv_ind = 0
for ind in ind_list:
    length = ind - prv_ind - 1
    tmp_matrix = pow_matrix(matrix, length, MOD)
    dp = calc(tmp_matrix, dp, MOD)
    for (row, flag) in blocks[ind]:
        if flag == 1:
            for i in range(3):
                matrix[row][i] = 0
        else:
            for i in range(3):
                matrix[row][i] = 1
            matrix[0][2] = 0
            matrix[2][0] = 0
    dp = calc(matrix, dp, MOD)
    prv_ind = ind
length = m - prv_ind - 1
tmp_matrix = pow_matrix(matrix, length, MOD)
dp = calc(tmp_matrix, dp, MOD)
print(dp[1] % MOD)

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline

def matmul(a, b, n):
    c = []
    for i in range(n):
        for j in range(n):
            x = 0
            for k in range(n):
                x += a[n * i + k] * b[n * k + j] % mod
            c.append(x)
    return c
(n, m) = map(int, input().split())
mod = pow(10, 9) + 7
d = defaultdict(lambda : 0)
pow2 = [1]
for _ in range(70):
    pow2.append(2 * pow2[-1])
d1 = defaultdict(lambda : 0)
d2 = defaultdict(lambda : 0)
d3 = defaultdict(lambda : 0)
for _ in range(n):
    (a, l, r) = map(int, input().split())
    if a == 1:
        d1[l - 1] += 1
        d1[r] -= 1
    elif a == 2:
        d2[l - 1] += 1
        d2[r] -= 1
    else:
        d3[l - 1] += 1
        d3[r] -= 1
l = -1
x = 0
for r in sorted(d1.keys()):
    x += d1[r]
    if x > 0:
        if l == -1:
            l = r
    else:
        d[l] ^= 1
        d[r] ^= 1
        l = -1
l = -1
x = 0
for r in sorted(d2.keys()):
    x += d2[r]
    if x > 0:
        if l == -1:
            l = r
    else:
        d[l] ^= 2
        d[r] ^= 2
        l = -1
l = -1
x = 0
for r in sorted(d3.keys()):
    x += d3[r]
    if x > 0:
        if l == -1:
            l = r
    else:
        d[l] ^= 4
        d[r] ^= 4
        l = -1
cc = []
for i in range(8):
    c0 = [1] * 9
    (c0[2], c0[6]) = (0, 0)
    for j in range(9):
        if pow2[j % 3] & i:
            c0[j] = 0
    cc0 = []
    cc0.append(c0)
    for _ in range(70):
        c0 = matmul(c0, c0, 3)
        cc0.append(c0)
    cc.append(cc0)
s = []
for i in d.keys():
    if d[i]:
        s.append(i)
s.sort()
l = 1
now = [0] * 9
now[4] = 1
x = 0
for r in s:
    lr = r - l
    cx = cc[x]
    i = 0
    while lr:
        if lr & pow2[i]:
            lr ^= pow2[i]
            now = matmul(now, cx[i], 3)
        i += 1
    x ^= d[r]
    l = r
lr = m - l
cx = cc[x]
i = 0
while lr:
    if lr & pow2[i]:
        lr ^= pow2[i]
        now = matmul(now, cx[i], 3)
    i += 1
ans = now[1] + now[4] + now[7]
ans %= mod
print(ans)

Solution (Python):
def mat_mul(A, B, mod):
    C = [[0] * len(B[0]) for i in range(len(A))]
    for i in range(len(A)):
        for k in range(len(B)):
            for j in range(len(B[0])):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
    return C

def mat_pow(A, n, mod):
    B = [[0] * len(A) for i in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1
    while n > 0:
        if n & 1 == 1:
            B = mat_mul(A, B, mod)
        A = mat_mul(A, A, mod)
        n = n >> 1
    return B
(n, m) = map(int, input().split())
mod = 10 ** 9 + 7
from collections import defaultdict
E = defaultdict(lambda : [])
for i in range(n):
    (a, l, r) = map(int, input().split())
    (a, l, r) = (a - 1, l - 1, r - 1)
    E[l].append((1, a))
    E[r + 1].append((-1, a))
E = list(E.items())
E.sort(key=lambda x: x[0])
block = [0] * 3
pos = 0
M = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
X = [0, 1, 0]
for (x, L) in E:
    A = mat_pow(M, x - 1 - pos, mod)
    nX = [0, 0, 0]
    for i in range(3):
        for j in range(3):
            nX[i] += X[j] * A[i][j]
            nX[i] %= mod
    X = nX
    for (t, a) in L:
        if t == 1:
            block[a] += 1
        else:
            block[a] -= 1
    if block[0] > 0:
        M[0] = [0, 0, 0]
    else:
        M[0] = [1, 1, 0]
    if block[1] > 0:
        M[1] = [0, 0, 0]
    else:
        M[1] = [1, 1, 1]
    if block[2] > 0:
        M[2] = [0, 0, 0]
    else:
        M[2] = [0, 1, 1]
    pos = x - 1
A = mat_pow(M, m - 1 - pos, mod)
nX = [0, 0, 0]
for i in range(3):
    for j in range(3):
        nX[i] += X[j] * A[i][j]
        nX[i] %= mod
X = nX
print(X[1] % mod)