链接：http://codeforces.com/problemset/problem/821/E
分析：由于有边界而且不同段边界还不同，直接算是不行的。。k是1e18，dp也不行。。用一个16维的向量表示某一列16个位置可能的种类数，到下一列的转移矩阵容易得到，而且在同一段里转移矩阵一样，直接用快速幂算出这一段结束的向量，然后继续推下一段结束的向量。注意特殊情况的处理。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 typedef long long ll; 5 const int maxn=105,p=1e9+7; 6 ll a[maxn],b[maxn],c[maxn]; 7 ll m[16][16],v[16]; 8 void initm(ll k){ 9 for(int i=0;i<16;i++) 10 for(int j=0;j<16;j++) 11 m[i][j]=0; 12 m[0][0]=1;m[0][1]=1; 13 for(int i=1;i<k;i++){ 14 m[i][i-1]=m[i][i]=m[i][i+1]=1; 15 } 16 if(k>0){ 17 m[k][k]=1;m[k][k-1]=1; 18 }else{ 19 m[0][1]=0; 20 } 21 } 22 void Copy(ll a[16][16],ll b[16][16]){ 23 for(int i=0;i<16;i++) 24 for(int j=0;j<16;j++) 25 a[i][j]=b[i][j]; 26 } 27 void multiply(ll ma[16][16],ll mb[16][16],ll ans[16][16]){ 28 ll a[16][16],b[16][16]; 29 Copy(a,ma);Copy(b,mb); 30 for(int i=0;i<16;i++){ 31 for(int j=0;j<16;j++){ 32 ans[i][j]=0; 33 for(int k=0;k<16;k++) 34 ans[i][j]=(ans[i][j]+a[i][k]*b[k][j])%p; 35 } 36 } 37 } 38 void print(ll a[16][16]){ 39 for(int i=0;i<16;i++){ 40 for(int j=0;j<16;j++) 41 cout<<a[i][j]<<' '; 42 cout<<endl; 43 } 44 } 45 void qpow(ll a[16][16],ll n,ll ans[16][16]){ 46 ll k=1,y[16][16]; 47 for(int i=0;i<16;i++){ 48 for(int j=0;j<16;j++) 49 ans[i][j]=0; 50 ans[i][i]=1; 51 } 52 Copy(y,a); 53 while(k){ 54 if(k&n){ 55 multiply(ans,y,ans); 56 //print(ans); 57 } 58 multiply(y,y,y); 59 k<<=1; 60 } 61 } 62 void Update(ll n,int h){ 63 initm(h); 64 ll M[16][16],v0[16]; 65 memset(v0,0,sizeof(v0)); 66 qpow(m,n,M); 67 for(int i=0;i<16;i++){ 68 for(int j=0;j<16;j++){ 69 v0[i]=(v0[i]+v[j]*M[i][j])%p; 70 } 71 } 72 for(int i=0;i<16;i++)v[i]=v0[i]; 73 } 74 int main(){ 75 int n; 76 ll aim; 77 memset(v,0,sizeof(v)); 78 v[0]=1; 79 cin>>n>>aim; 80 for(int i=0;i<n;i++){ 81 cin>>a[i]>>b[i]>>c[i]; 82 if(i==n-1)b[i]=aim; 83 Update(b[i]-a[i],c[i]); 84 } 85 cout<<v[0]<<endl; 86 return 0; 87 }