首先我们从最简单的dp开始
\(dp[i][j]=dp[i-1][j]+dp[i-1][j+1]+dp[i-1][j-1]\)
然后这是一个O(NM)的做法，肯定行不通，然后我们考虑使用矩阵加速
\(\begin{bmatrix} 1\\ 0 \\0\\0\end{bmatrix}\quad\)
鉴于纵坐标很小，考虑全部记录下来。写成一个向量的形式。如上，
第i行的数表示纵坐标为i-1的方案数。然后我们考虑转移
\(\begin{bmatrix} 1&1&0&0\\1&1&1&0 \\0&1&1&1\\0&0&1&1\end{bmatrix}\quad\)
我们将不考虑线段的转移写成以上形式，然后考虑一下如果有线段影响呢？
我们可以类比得到，上一个矩阵中的边界是3，如果我们人为规定上边界是2的话。转移就成了这个样子
\(\begin{bmatrix} 1&1&0&0\\1&1&1&0 \\0&1&1&0\\0&0&0&0\end{bmatrix}\quad\)
然后我们发现，如果不是上边界和下边界时，matrix[i][i].matrix[i][i-1].matrix[i][i+1]都是1，然后上下边界自己处理就可以了。
然后我们上一个矩阵快速幂就可以了
#include#include #include using namespace std;const long long mod=1e9+7;struct node{ int n,m; long long base[20][20]; node operator * (const node &a)const { node r; r.n=n,r.m=a.m; for(int i=0;i<=n;i++) for(int j=0;j<=a.m;j++) r.base[i][j]=0; for(int i=1;i<=n;i++) for(int j=1;j<=a.m;j++) for(int k=1;k<=m;k++) r.base[i][j]=(r.base[i][j]+base[i][k]*a.base[k][j])%mod; return r; }};//矩阵模板node pas,ans;long long a[120],b[120],c[120];node kasumi(long long k){ node res; res.n=res.m=pas.n; for(int i=0;i<=res.n;i++) for(int j=0;j<=res.m;j++) res.base[i][j]=0; for(int i=0;i<=res.n;i++) res.base[i][i]=1; while(k) { if(k&1) res=res*pas; pas=pas*pas; k>>=1; } return res;//快速幂}int main(){ long long n,k; scanf("%lld%lld",&n,&k); ans.n=1;ans.m=16; for(int i=1;i<=16;i++) for(int j=1;j<=16;j++) ans.base[i][j]=0;//读入数据 ans.base[1][1]=1;//处理初始数据 pas.n=16;pas.m=16; for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);//输入 for(int l=1;l<=n;l++)//然后按照顺序遍历线段 { for(int i=0;i<=16;i++) for(int j=0;j<=16;j++) pas.base[i][j]=0;//重新清零 for(int i=1;i<=c[l]+1;i++) {//处理转移数组 if(i!=1) pas.base[i][i-1]=1; pas.base[i][i]=1; if(i!=c[l]+1) pas.base[i][i+1]=1; } ans=ans*kasumi(min(b[l],k)-a[l]);//快速幂就可以了 } printf("%lld",ans.base[1][1]);}