Submission #68638835

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
struct Matrix{
	int n,m,a[4][4];
	Matrix(){
		memset(a,0,sizeof(a)); 
	}
	Matrix(int _n,int _m){
		n=_n,m=_m;
		memset(a,0,sizeof(a));
	}
	Matrix operator * (Matrix b){
		Matrix c(n,b.m);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				for(int k=1;k<=b.m;k++){
					c.a[i][k]=(c.a[i][k]+a[i][j]*b.a[j][k]%mod)%mod;
				}
			}
		}
		return c;
	}
};
int n,m,x[100005];
void trans(Matrix &f){
	f.a[1][3]+=(f.a[1][2]+f.a[1][1])%mod;
	f.a[1][3]%=mod;
	f.a[1][2]+=2*f.a[1][1]%mod;
	f.a[1][2]%=mod;
}
Matrix ksm(Matrix op,int b){
	Matrix res(3,3);
	res.a[1][1]=res.a[2][2]=res.a[3][3]=1;
	while(b){
		if(b&1) res=res*op;
		op=op*op;
		b/=2;
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x[i];
	}
	int lst=1;
	Matrix f(1,3);
	f.a[1][1]=1,f.a[1][2]=2,f.a[1][3]=1;
	Matrix op(3,3);
	op.a[1][1]=op.a[2][2]=op.a[2][3]=op.a[1][3]=op.a[3][1]=1;
	op.a[1][2]=op.a[3][2]=op.a[3][3]=2;
//	for(int i=2;i<=n;i++){
//		f=f*op;
//		for(int j=1;j<=3;j++) cout<<f.a[1][j]<<" ";
//		cout<<"\n";
//	}
	for(int i=1;i<=m;i++){
		f=f*ksm(op,x[i]-lst);
		trans(f);
		lst=x[i]+1;
	}
//	cout<<n-lst<<"\n";
//	 Matrix tmp=ksm(op,n-lst);
//	 for(int i=1;i<=3;i++){
//	 	for(int j=1;j<=3;j++){
//	 		cout<<tmp.a[i][j]<<" ";
//		 }
//		 cout<<"\n";
//	 }
//	 cout<<f.a[1][1]<<" "<<f.a[1][2]<<" "<<f.a[1][3]<<"\n";
	f=f*ksm(op,n-lst);
	cout<<f.a[1][3]<<"\n";
} 

Submission Info

Judge Result