题意 ：你从起点(0,0)走到终点(k,0)，其中你每次只可以走右边，右上，右下三个位置，并且有一个附加条件，对于对应的区间，y有个上限。

思路： 看这题一开始有点像搜索，算算复杂度和实现方法，很麻烦。 因为每次你所能到达位置的方案数和前面能到这个点的方案数有关，因此可以用dp做。 状态转移方程为 dp[i][j]=dp[i-1][j]+dp[i-1][j+1]+dp[i-1][j-1],状态转移方程很容易，复杂度却达到O(k) (k<=1e18) 明显超时。因此对于这题，y很小，k很大，因此可以用矩阵快速幂来来优化dp过程，复杂度自最差变为O(n*(15)^3log(k))≈2e7 ;一个log ， 把k降低到只要60左右， 太强了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD=1e9+7;
typedef struct
{
    ll mat[20][20];
}matrix;

// 矩阵乘法
matrix matrix_mul(matrix a,matrix b,ll y)
{
    matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(ll i=0;i<=y;i++)
    {
        for(ll j=0;j<=y;j++)
        {
            for(ll k=0;k<=y;k++)
            {
                c.mat[i][j]+=(a.mat[i][k]%MOD*b.mat[k][j]%MOD)%MOD;
                c.mat[i][j]%=MOD;
            }
        }
    }
    return c;
}

// 快速幂
matrix matrix_quick_power(matrix a,ll k ,ll y)
{
    matrix b;
    memset(b.mat,0,sizeof(b.mat));
    for(int i=0;i<=15;i++)
        b.mat[i][i]=1;
    while(k)
    {
        if(k%2==1)  b=matrix_mul(b,a,y);
        k=k/2;
        a=matrix_mul(a,a,y);
    }
    return b;

}

matrix a,b,c;
int main(void)
{
    ll n,k;
    cin >> n >>k;
    memset(a.mat,0,sizeof(a.mat));
    for(int i=0;i<=15;i++)
        for(int j=i-1;j<=i-1+2;j++)
            if(j>=0 && j<=15)
                a.mat[i][j]=1;
    /*for(int i=0;i<=15;i++) { for(int j=0;j<=15;j++) printf("%d ",a.mat[i][j]); puts(""); }*/
    c.mat[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        ll  l,r,y;
        scanf("%I64d%I64d%I64d",&l,&r,&y);
        if(r>k)  r=k;
        for(int i=y+1;i<=18;i++)    c.mat[0][i]=0; // 一定要这么处理，否则对于y为 5 2 6 中，5的结果会对6造成影响。
        b=matrix_quick_power(a,r-l,y);
        c=matrix_mul(b,c,y);
    }
    printf("%I64d\n",c.mat[0][0]%MOD);
}

1.学习到了矩阵快速幂，其实和数的快速幂原理几乎一样。
矩阵快速幂适合作用于有递推方程的，并且dp[i] 的i范围比较小的情况，对于这道题，i最多只有15，k=1e18,dp次数很多。所以很明显用dp+矩阵快速幂了
2.第一次做了E题，其实也没有那么难啊~
3.今天被猫抓了.,.. 打了两针疫苗