Submission #1520998

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define MOD 1000000007LL 
#define MODMOD MOD*MOD
const int matrix_size = 4;
struct matrix{
	int mat[matrix_size][matrix_size];  //caution!
	matrix(){
		memset(mat, 0, sizeof(mat));
	}
};
matrix operator *(const matrix &a, const matrix &b){
	matrix r;
	long long int tmp;
	for (int i = 0; i < matrix_size; i++){
		for (int j = 0; j < matrix_size; j++){
			tmp = 0;
			for (int k = 0; k < matrix_size; k++){
				tmp += (long long int)(a.mat[i][k]) * b.mat[k][j];
				if (tmp >= MODMOD)tmp -= MODMOD;
			}
			if (tmp >= MOD)tmp %= MOD;
			r.mat[i][j] = tmp;
		}
	}
	return r;
}
matrix operator +(const matrix &a, const matrix &b){
	matrix r;
	for (int i = 0; i < matrix_size; i++){
		for (int j = 0; j < matrix_size; j++){
			r.mat[i][j] += a.mat[i][j] + b.mat[i][j];
			if (r.mat[i][j] >= MOD){
				r.mat[i][j] -= MOD;
			}
		}
	}
	return r;
}
matrix ppow(matrix i, long long int j){
	if (j == 0){
		for (int i1 = 0; i1<matrix_size; i1++){
			for (int j = 0; j<matrix_size; j++){
				i.mat[i1][j] = (i1 == j);
			}
		}
		return i;
	}
	if (j == 1LL){
		return i;
	}
	j--;
	matrix r = i;
	while (j){
		if ((j & 1LL)){
			r = r*i;
		}
		i = i*i;
		j >>= 1LL;
	}
	return r;
}
int n;
int m;

vector<int> x;
matrix base;
matrix base2;
int main(){
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		int a;
		scanf("%d", &a);
		x.push_back(a);
	}
	//zero
	//one
	//two
	//all
	base.mat[3][0] = 1;
	base.mat[1][3] = 1;
	base.mat[2][3] = 1;
	base.mat[0][1] = base.mat[0][2] = base.mat[0][3] = 1;
	base.mat[0][0] = base.mat[1][1] = base.mat[2][2] = base.mat[3][3] = 1;
	base2 = base;
	base2.mat[3][0] = base2.mat[3][1] = base2.mat[3][2] = 0;
	base.mat[0][0]++;
	base.mat[1][0] = base.mat[2][0] = 1;
	matrix base3;
	base3.mat[0][0] = base3.mat[1][1] = base3.mat[2][2] = base3.mat[3][3] = 1;
	int cur = n;
	for (int i = (int)(x.size()) - 1; i >= 0; i--){
		base3 = base3*ppow(base, cur-x[i]-1);
		base3 = base3*base2;
		cur = x[i];
	}
	base3 = base3*ppow(base, cur);
	long long int ans = base3.mat[0][3];
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:74:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^

Judge Result