原题大意

从（0,0）到（k，0），每个点可以到达右上，右，右下这三个点，但必须在c下方，0上方（包括0边界），问最终到达（k，0）有多少种方案。

算法分析

dp，因为ci是一条与x轴平行的线段，所以从ai到ai+1的每一次的贡献都是一样的，可以用矩阵加速，c最多为15，所以不会超时

程序代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
struct matrix{
  ll val[16][16];
  matrix(){memset(val,0,sizeof(val));}
  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.val[i][j] += val[i][k] * rhs.val[k][j]%mod,
          ret.val[i][j] %= mod;
    return ret;
  }
};
matrix pow_mod(const matrix& b, ll p){
  matrix ret, cur = b;
  for(int i = 0; i < 16; i++)
    ret.val[i][i] = 1;
  while(p){
    if(p & 1)
      ret = ret * cur;
    cur = cur * cur;
    p>>=1;
  }
  return ret;
}
int n;
ll k;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  cin >> n >> k;
  matrix ans;
  ans.val[0][0] = 1;
  for(int i = 1; i <= n; i++){
    ll a, b;
    int c;
    cin >> a >> b >> c;
    matrix mul;
    for(int j = 0; j <= c; j++)
      for(int l = j-1; l <= j+1; l++)
        if(l >= 0 && l <= c)
          mul.val[j][l] = 1;
    ans = pow_mod(mul, min(b,k) - a) * ans;
  }
  cout << ans.val[0][0] << endl;
  return 0;
}