Codeforces Round #420 (Div. 2) E. Okabe and El Psy Kongroo

http://codeforces.com/contest/821/problem/E

(0,0) 에서 (k,0) 까지 가는 방법의 수를 구하는 문제이다.

이동을 할 때에는 세가지 방법이 가능하다. (x,y) 에서 (x+1,y-1), (x+1,y), (x+1, y+1) 이렇게 세가지 이동이 가능하다.

대신 n개의 선분이 주어진다. 구간은 ai, bi, ci 로 표현되며

y좌표가 ci 이면서 x좌표가 [ai,bi] 인 선분이다. 출발지에서 도착지까지 갈 때

이 선분을 넘어가면 안된다. \(b_i = a_{i+1} \) 라는 조건과 \(a_n \le {k}\le{b_n}\) 라는 조건이 주어진다.

그리고 ci 는 최대 15이며 ai,bi,k 는 10^18 이하이다.

뻔한 행렬 dp 이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
struct matrix{
    int mat[16][16];
    matrix(){
        memset(mat,0,sizeof(mat));
    }
    matrix(int h){
        memset(mat,0,sizeof(mat));
        if(h == 1){
            mat[0][0] = 1;
        }    
        else if(h == 2){
            mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 1;
        }
        else{
            mat[0][0] = mat[0][1] = mat[h-1][h-2] = mat[h-1][h-1] = 1;
            for(int i = 1 ; i < h-1; i++){
                for(int j = i-1; j <= i+1; j++){
                    mat[i][j] = 1;
                }
            }
        }
    }
    matrix operator*(const matrix& rhs) const{
        matrix ret;
        for(int i = 0 ; i < 16; i++) {
            for(int j = 0 ; j < 16; j++){
                for(int k = 0 ; k < 16; k++){
                    ret.mat[i][j] = (ret.mat[i][j] + (ll)mat[i][k] * rhs.mat[k][j] ) % mod;
                }
            }
        }
        return ret;
    }
};
matrix I;
matrix matpow(matrix mat, ll k){
    if(!k) return I;
    if(k%2) return mat*matpow(mat, k-1);
    return matpow(mat*mat, k/2);
}
int n;
ll k;
int main() {
    cin >> n >> k;
    for(int i = 0 ; i < 16; i++) I.mat[i][i] = 1;
    matrix res = I;
    for(int i = 0 ; i < n ; i++){
        ll a,b;
        int c;
        cin >> a >> b >> c;
        if(b > k) b = k;
        matrix mat(c+1);
        res = matpow(mat, b-a) * res;
    }
 
    cout << res.mat[0][0];
    return 0;
}