【codefoces821E】 Okabe and El Psy Kongroo【Dp+矩阵快速幂】

本文主要是介绍【codefoces821E】 Okabe and El Psy Kongroo【Dp+矩阵快速幂】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://vjudge.net/problem/CodeForces-821E
题意：
我们现在位于（0,0）处，目标是走到（K，0）处。
每一次我们都可以从（x，y）走到（x+1，y-1）或者（x+1，y）或者（x+1，y+1）三个位置之一，且 y <= c [ i ] 。
问我们从起点走到终点的行走方案数。
题解：
我也分不清这改叫递推还是DP
总之方程很好写
Dp [ i ] [ j ]=Dp[ i-1 ] [ j ] + Dp [ i-1 ] [ j-1 ] +Dp [ i-1 ] [ j+1 ]
但是 $k\leq 10^{18}$ 是跑不过的，这样的线性递推，而且（i，j）只和（i-1 , j）,（i-1 , j-1），（i-1 . j+1）有关，显然可以用矩阵快速幂优化
构建一个类似的矩阵

⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ 110 ⋮ 000 111 ⋮ 000 011 ⋮ 000 001 ⋮ 000 000 ⋮ 000 \dots \dots \dots ⋱ \dots \dots \dots 000 ⋮ 100 000 ⋮ 110 000 ⋮ 111 000 ⋮ 011 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥

$\left[ \begin{matrix}1 & 1 &0&0&0 & \cdots &0& 0 &0 &0 \\1 & 1&1&0&0 & \cdots &0& 0 &0 &0\\0&1&1&1&0&\cdots&0&0&0&0\\\vdots & \vdots & \vdots& \vdots& \vdots& \ddots & \vdots& \vdots&\vdots & \vdots \\0 & 0 & 0&0&0&\cdots & 1&1 &1&0 \\0 & 0 & 0&0&0&\cdots &0& 1&1 &1 \\0 & 0 & 0&0&0&\cdots &0&0& 1&1 \\ \end{matrix} \right]$
以c【】数组限制矩阵宽，每次要把不合法状态清零，记得矩阵初始化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long longconst LL mod=1e9+7;
struct Matrix
{LL m[17][17];
};
Matrix mul(Matrix a,Matrix b,LL n)
{Matrix ans;memset(ans.m,0,sizeof(ans.m));for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)(ans.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod)%=mod;return ans;         
}Matrix ksm(Matrix a,LL b,LL n)
{Matrix ans;memset(ans.m,0,sizeof(ans.m));for(int i=0;i<=n;i++)ans.m[i][i]=1;while(b){if(b&1) ans=mul(ans,a,n);a=mul(a,a,n);b>>=1;  }return ans;
}int main()
{int n,flag=0;LL k,a,b,c;Matrix e,f,g;memset(e.m,0,sizeof(e.m));for(int i=0;i<=16;i++)for(int j=i-1;j<=i+1;j++)if(j>=0&&j<=16)e.m[i][j]=1;memset(f.m,0,sizeof(f.m));f.m[0][0]=1;scanf("%d%lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&a,&b,&c);if(b>k) b=k,flag=1;g=ksm(e,b-a,c);for(int j=c+1;j<=16;j++) f.m[j][0]=0;g=mul(g,f,c);for(int j=0;j<=c;j++)    f.m[j][0]=g.m[j][0];if(flag==1) break;}       printf("%lld\n",g.m[0][0]);return 0;
}