本文主要是介绍Codeforces Round #420 (Div. 2) E. Okabe and El Psy Kongroo（矩阵快速幂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/821/problem/E
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]然后构造矩阵转移就行了。。。貌似没啥难度？
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
const int MOD=1e9+7;
typedef long long ll;
ll a[MAXN],b[MAXN];
int c[MAXN];
struct Matrix
{ll a[16][16];Matrix(){for(int i=0;i<16;i++)for(int j=0;j<16;j++)a[i][j]=0;}Matrix operator * (const Matrix &B)const{Matrix C;for(int i=0;i<16;i++)for(int k=0;k<16;k++)for(int j=0;j<16;j++)C.a[i][j]=(C.a[i][j]+(a[i][k]*B.a[k][j])%MOD)%MOD;return C;}Matrix operator + (const Matrix &B)const{Matrix C;for(int i=0;i<16;i++)for(int j=0;j<16;j++)C.a[i][j]=(a[i][j]+B.a[i][j])%MOD;return C;}Matrix operator % (const ll &t)const{Matrix A=(*this);for(int i=0;i<16;i++){for(int j=0;j<16;j++){A.a[i][j]%=MOD;}}return A;}Matrix operator ^ (const ll &t)const{Matrix A=(*this),res;for(int i=0;i<16;i++){res.a[i][i]=1;}ll p=t;while(p){if(p&1)res=res*A;A=A*A;p>>=1;}return res;}void reset(int lim){clear();for(int i=0;i<=lim;i++){if(i-1>=0)a[i][i-1]=1;a[i][i]=1;if(i+1<=lim)a[i][i+1]=1;}}void clear(){memset(a,0,sizeof(a));}
}ans,tmp,mo;
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n;ll k;scanf("%d%lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld%lld%d",&a[i],&b[i],&c[i]);}tmp.clear();tmp.a[0][0]=1;for(int i=1;i<=n;i++){ans.clear();for(int j=0;j<=c[i];j++){ans.a[0][j]=tmp.a[0][j];}mo.reset(c[i]);mo=(mo)^(min(k,b[i])-a[i]);ans=ans*mo;tmp.clear();for(int j=0;j<=c[i];j++){tmp.a[0][j]=ans.a[0][j];}//printf("%lld\n",ans.a[0][0]);}printf("%lld\n",ans.a[0][0]);return 0;
}
这篇关于Codeforces Round #420 (Div. 2) E. Okabe and El Psy Kongroo（矩阵快速幂）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
