题目链接：点击打开链接
题意：
•在一个二维xoy第一象限平面上(即x,y必须保持非负)，你一开始在原点(0,0)，每一次可以从(x,y)往右跳到(x+1,y)，也可以向右上角跳到(x+1,y+1)，也可以向右下角跳到(x+1,y-1),然后还有n条平行于x轴的线段(a,b,c)，分别在(a,c)-(b,c)上，当你的横坐标在[a,b]区间时，y坐标不能超过c，问有多少种方案到达(k,0)。结果对10^9+7取余 •(1<=n<=100,0<=c<=15,0<=a,b,k<=10^18,a[i]=b[i-1],a[0]=0) 思路：dp+矩阵快速幂
比较裸的dp+矩阵快速幂，因为这里k为1e18，所以几乎只能用矩阵快速幂来做了。
朴素的dp，dpij表示走到(i, j)时的方案数，
则 状态方程为，if(j+1 <= b[k]) dp[i+1][j+1] += dp[i][j];
if(j-1 >= 0) dp[i+1][j-1] += dp[i][j];
dp[i+1][j] += dp[i][j];
然后可以构造出15*15(ci<=15)的矩阵，把状态转移到矩阵上，然后对于每个a[k]、b[k]、c[k]跑一次快速幂即可。
此外注意a[k]，b[k]，以及快速幂的参数到是LL。
复杂度 O(n*(15)^3*log(k))
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> using namespace std; #define ll long long #define N 25 #define maxn 300 ll mod=1000000007; ll n,k; struct Matrix { ll r,c; ll m[N][N]; Matrix(){} Matrix(ll r,ll c):r(r),c(c){} Matrix operator *(const Matrix& B)//乘法 { Matrix T(r,B.c); for(int i=1;i<=T.r;i++) { for(int j=1;j<=T.c;j++) { ll tt = 0; for(int k=1;k<=c;k++) tt +=( m[i][k]*B.m[k][j]) % mod; T.m[i][j] = tt % mod; } } return T; } Matrix operator =(const Matrix& B)//复制 { for(int i=1;i<=r;i++) { for(int j=1;j<=c;j++) { m[i][j] = B.m[i][j]; } } } Matrix operator +(const Matrix& B)//加法 { for(int i=1;i<=r;i++) { for(int j=1;j<=c;j++) { m[i][j]+= B.m[i][j]; } } } Matrix Unit(ll h) // 对角线矩阵 { Matrix T(h,h); memset(T.m,0,sizeof(T.m)); for(int i=1;i<=h;i++) T.m[i][i] = 1; return T; } Matrix Pow(ll n) //矩阵幂 { Matrix P = *this,Res = Unit(r); while(n!=0) { if(n&1) Res =Res*P; P = P*P; n >>= 1; } return Res; } void Print()//输出 { for(int i=1;i<=r;i++) { for(int j=1;j<=c;j++) printf("%d ",m[i][j]); printf("\n"); } } }Single; ll u[maxn],v[maxn],h[maxn]; int main(){ while(~scanf("%lld%lld",&n,&k)) { for(int i=0;i<n;i++) { scanf("%lld%lld%lld",&u[i],&v[i],&h[i]); h[i]++; } Matrix a(17,17),b(1,17); memset(b.m,0,sizeof b.m); b.m[1][1]=1; for(int i=0;i<n;i++) { memset(a.m,0,sizeof a.m); for(int j=1;j<=h[i];j++) { if(j+1<=h[i]) { a.m[j][j+1]=1; } if(j-1>=1) { a.m[j][j-1]=1; } a.m[j][j]=1; } if(k<v[i]) b=b*a.Pow(k-u[i]); else b=b*a.Pow(v[i]-u[i]); } cout<<b.m[1][1]<<endl; //printf("%lld\n",b.m[1][1]); } return 0; }
