提出 #18990974

---

ソースコード 拡げる

/*
after dusk passed,
there is a starry sky.
*/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define m_k make_pair
#define mod 1000000007
#define int long long
using namespace std;
int n,m;
inline void add(int &a,int b){a=((a+b>=mod)?a+b-mod:a+b);}
inline void del(int &a,int b){a=((a-b<0)?a-b+mod:a-b);}
inline void mul(int &a,int b){a=a*b%mod;}
inline int m_pow(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) mul(ans,a);
		b>>=1;
		mul(a,a);
	}
	return ans;
}
struct matrix
{
	int a[4][4];
	inline void clear(){memset(a,0,sizeof(a));}
	inline void init(){clear();for (int i=1;i<=3;i++) a[i][i]=1;}
	inline void get(int kind)
	{
		for (int i=1;i<=3;i++) for (int j=1;j<=3;j++) a[i][j]=1;
		a[1][2]=2;a[2][1]=a[3][1]=a[3][2]=0;
		if (kind==2) for (int i=1;i<=3;i++) a[i][1]++;
	}
}A;
matrix B,ans;
matrix operator *(matrix a,matrix b)
{
	matrix ans;ans.clear();
	for (int i=1;i<=3;i++)
	{
		for (int k=1;k<=3;k++)
		{
			for (int j=1;j<=3;j++) add(ans.a[i][j],a.a[i][k]*b.a[k][j]%mod);
		}
	}
	return ans;
}
matrix m_pow(matrix a,int b)
{
	matrix ans;ans.init();
	while (b)
	{
		if (b&1) ans=ans*a;
		b>>=1;
		a=a*a;
	}
	return ans;
}
inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
signed main()
{
	n=read();m=read();
	A.get(1);B.get(2);
	ans.a[1][1]=1;
	int last=0;
	for (int i=1;i<=m;i++)
	{
		int x=read();
		ans=ans*m_pow(B,x-last-1)*A;
		last=x;
	}
	ans=ans*m_pow(B,n-last);
	printf("%lld\n",ans.a[1][3]);
}

提出情報

ジャッジ結果