题目链接：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段线段，每条线段都是平行于X轴的。我们如果此时x是在这段线段之内的话，我们此时走到的点（x，y）需要满足0<=y<=Ci.
现在保证一段线段的终点，一定是下一段线段的起点。问我们从起点走到终点的行走方案数。
题解：简单的dp+矩阵快速幂的模版
显然如果k很小是个很简单的dp,dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1]。但是k很大所以就要用到矩阵快速幂，一般像这种递推方程式都是可以化为用矩阵来求的
dp[1] 110000000000000 predp[1]
dp[2] 111000000000000 predp[2]
dp[3] 011100000000000 predp[3]
dp[4] 001110000000000 predp[4]
.
.
.
dp[15] 000000000000011 predp[15]
#include <iostream>
#include <cstring>
#include <cstdio>
#define mod 1000000007
using namespace std;
typedef long long ll;
struct Matrix {
ll dp[17][17];
};
Matrix Mul(Matrix a , Matrix b , ll Max) {
Matrix c;
memset(c.dp , 0 , sizeof(c.dp));
for(ll i = 0 ; i <= Max ; i++) {
for(ll j = 0 ; j <= Max ; j++) {
for(int k = 0 ; k <= Max ; k++) {
c.dp[i][j] += ((a.dp[i][k]) % mod * (b.dp[k][j]) % mod) % mod;
c.dp[i][j] %= mod;
}
}
}
return c;
}
Matrix Matrix_quick_pow(Matrix a , ll k , ll Max) {
Matrix res;
memset(res.dp , 0 , sizeof(res.dp));
for(ll i = 0 ; i <= Max ; i++) res.dp[i][i] = 1;
while(k) {
if(k & 1) res = Mul(res , a , Max);
k >>= 1;
a = Mul(a , a , Max);
}
return res;
}
int main() {
ll n , k;
scanf("%lld%lld" , &n , &k);
Matrix ans , ope , pre;
memset(ope.dp , 0 , sizeof(ope.dp));
memset(pre.dp , 0 , sizeof(pre.dp));
for(int i = 0 ; i < 16 ; i++) {
if(i == 0) {
ope.dp[i][i] = 1;
ope.dp[i][i + 1] = 1;
}
else if(i == 15) {
ope.dp[i][i] = 1;
ope.dp[i][i - 1] = 1;
}
else {
ope.dp[i][i] = 1;
ope.dp[i][i + 1] = 1;
ope.dp[i][i - 1] = 1;
}
}
pre.dp[0][0] = 1;
for(int i = 1 ; i <= n ; i++) {
ll a , b , Max , flag = 0;
scanf("%lld%lld%lld" , &a , &b , &Max);
if(b > k) {b = k , flag = 1;}
ans = Matrix_quick_pow(ope , b - a , Max);
for(ll j = Max + 1 ; j < 16 ; j++) pre.dp[j][0] = 0;
ans = Mul(ans , pre , Max);
for(ll j = 0 ; j <= Max ; j++) {
pre.dp[j][0] = ans.dp[j][0];
}
if(flag) break;
}
printf("%lld
" , ans.dp[0][0]);
return 0;
}