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

题目链接：Codeforces Round #420 (Div. 2) E. Okabe and El Psy Kongroo

题意：

在一个二维方格子里有n条线段，有三种走法

(x + 1, y + 1), (x + 1, y), or (x + 1, y - 1).

现在要求每次都要在线段下行走，问你有多少种走法，

可以从(0,0)到(k,0)。

题解：

考虑dp f[i][j]=f[i-1][j]+f[i-1][j+1]+f[i-1][j-1]。

由于k比较大c比较小，可以考虑用矩阵来优化。

将每一个y_i看做一个向量。过渡矩阵满足上面的DP方程即可。

这样就可以快速的处理每条线段的状态转移。

然后再对每两条线段的过度处理一下就行了。

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define F(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
typedef long long ll;

const int mat_N=16,mo=1e9+7;
struct mat{
    ll c[mat_N][mat_N];
    void init(){mst(c,0);}
    mat operator*(mat b){
        mat M;int N=mat_N-1;M.init();
        F(i,0,N)F(j,0,N)F(k,0,N)M.c[i][j]=(M.c[i][j]+c[i][k]*b.c[k][j])%mo;
        return M;
    }
    mat operator^(ll k){
        mat ans,M=(*this);int N=mat_N-1;ans.init();
        F(i,0,N)ans.c[i][i]=1;
        while(k){if(k&1)ans=ans*M;k>>=1,M=M*M;}
        return ans;
    }
}TR,now;

int n;
ll ans[16],tmp[16],k;

void del(int h)
{
    TR.init();
    F(i,15-h,15)
    {
        if(i-1>=0)TR.c[i][i-1]=1;
        TR.c[i][i]=1;
        if(i+1<=15)TR.c[i][i+1]=1;
    }
}

int main()
{
    scanf("%d%I64d",&n,&k);
    ans[15]=1;
    F(i,1,n)
    {
        ll l,r,h;
        scanf("%I64d%I64d%I64d",&l,&r,&h);
        del(h),now=TR^(min(r-l,k-l));
        F(i,0,(14-h))ans[i]=0;
        F(i,0,15)
        {
            tmp[i]=0;
            F(j,0,15)tmp[i]+=(now.c[i][j]*ans[j])%mo;
            tmp[i]%=mo;
        }
        F(i,0,15)ans[i]=tmp[i];
        if(k<r)break;    
    }
    printf("%I64d
",ans[15]);
    return 0;
}