Submission #1224501

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <string>
#define SIZE 100005
#define MOD 1000000007
#define MX 5

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct Matrix
{
	int n;
	ll A[MX][MX];
	
	ll mpow(ll x,ll t)
	{
		if(t==0) return 1;
		ll ret=mpow(x,t/2);
		ret=ret*ret%MOD;
		if(t%2==1) ret=ret*x%MOD;
		return ret;
	}
	ll inv(ll x)
	{
		return mpow(x,MOD-2);//if MOD is a prime number
	}
	void init(int m)
	{
		n=m;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				A[i][j]=0;
			}
		}
	}
	void add(int a,int b,ll x)
	{
		A[a][b]+=x;
		if(A[a][b]>=MOD) A[a][b]-=MOD;
	}
};
Matrix SUM_mat,PR_mat;
void product(Matrix&A,Matrix&B)
{
	int n=A.n;
	PR_mat.init(n);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			PR_mat.A[i][j]=0;
			for(int k=0;k<n;k++)
			{
				PR_mat.A[i][j]+=A.A[i][k]*B.A[k][j]%MOD;
				if(PR_mat.A[i][j]>=MOD) PR_mat.A[i][j]-=MOD;
			}
		}
	}
}
void sumsum(Matrix&A,Matrix&B)
{
	int n=A.n;
	SUM_mat.init(n);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			SUM_mat.A[i][j]=0;
			for(int k=0;k<n;k++)
			{
				SUM_mat.A[i][j]+=(A.A[i][k]+B.A[k][j])%MOD;
				if(SUM_mat.A[i][j]>=MOD) SUM_mat.A[i][j]-=MOD;
			}
		}
	}
}
Matrix mt[1000];
void mpow(Matrix&M,ll t,int dep)
{
	if(t==1)
	{
		mt[dep]=M;
		return;
	}
	mpow(M,t/2,dep+1);
	product(mt[dep+1],mt[dep+1]);
	mt[dep]=PR_mat;
	if(t%2==1)
	{
		product(mt[dep],M);
		mt[dep]=PR_mat;
	}
}

int main()
{
	ll eA=0,eB=1,eC=3;
	ll oA=0,oB=0,oC=0;
	Matrix M;
	M.init(3);
	M.add(0,0,4);
	M.add(0,1,MOD-2);
	M.add(0,2,1);
	M.add(1,0,1);
	M.add(1,1,0);
	M.add(1,2,0);
	M.add(2,0,0);
	M.add(2,1,1);
	M.add(2,2,0);
	int n,m;
	scanf("%d %d",&n,&m);
	int bef=0;
	for(int i=0;i<m;i++)
	{
		int x;
		scanf("%d",&x);
		mpow(M,x-bef,0);
		ll na=(mt[0].A[0][0]*eA%MOD+mt[0].A[0][1]*eB%MOD+mt[0].A[0][2]*eC%MOD)%MOD;
		ll nb=(mt[0].A[1][0]*eA%MOD+mt[0].A[1][1]*eB%MOD+mt[0].A[1][2]*eC%MOD)%MOD;
		ll nc=(mt[0].A[2][0]*eA%MOD+mt[0].A[2][1]*eB%MOD+mt[0].A[2][2]*eC%MOD)%MOD;
		
		ll ma=(mt[0].A[0][0]*oA%MOD+mt[0].A[0][1]*oB%MOD+mt[0].A[0][2]*oC%MOD)%MOD;
		ll mb=(mt[0].A[1][0]*oA%MOD+mt[0].A[1][1]*oB%MOD+mt[0].A[1][2]*oC%MOD)%MOD;
		ll mc=(mt[0].A[2][0]*oA%MOD+mt[0].A[2][1]*oB%MOD+mt[0].A[2][2]*oC%MOD)%MOD;
		
		eA=na,eB=(nb+ma)%MOD,eC=(nc+3LL*ma)%MOD;
		oA=ma,oB=(mb+na)%MOD,oC=(mc+3LL*na)%MOD;
		
		bef=x;
	}
	mpow(M,n-bef,0);
	ll na=(mt[0].A[0][0]*eA%MOD+mt[0].A[0][1]*eB%MOD+mt[0].A[0][2]*eC%MOD)%MOD;
	ll ma=(mt[0].A[0][0]*oA%MOD+mt[0].A[0][1]*oB%MOD+mt[0].A[0][2]*oC%MOD)%MOD;
	printf("%lld\n",(na-ma+MOD)%MOD);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:123:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
./Main.cpp:128:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
                 ^

Judge Result