1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using ll = long long;
const ll ha = 1000000007LL;
typedef ll Mat[3][3];
void (Mat A, Mat B, int n, int m, int p, Mat &res) {
static Mat C; memset(C, 0, sizeof(C));
for(int i = 0; i < n; i ++) {
for(int j = 0; j < p; j ++) {
for(int k = 0; k < m; k ++) {
C[i][j] += A[i][k] * B[k][j] % ha;
if(C[i][j] >= ha) C[i][j] -= ha;
}
}
}
memcpy(res, C, sizeof(C));
}
void mat_pow(Mat A, int n, int c, Mat &res) {
static Mat C, a; memset(C, 0, sizeof(C));
for(int i = 0; i < n; i ++) C[i][i] = 1;
memcpy(a, A, sizeof(a));
while(c) {
if(1 & c) mat_mul(C, a, n, n, n, C);
mat_mul(a, a, n, n, n, a); c >>= 1;
}
memcpy(res, C, sizeof(C));
}
Mat A, C, T, B;
std::vector<int> V;
int main() {
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int x; scanf("%d", &x);
V.push_back(x);
}
V.push_back(n);
int las = 0;
A[0][0] = 1;
A[1][0] = 2; A[1][1] = 1;
A[2][0] = A[2][1] = A[2][2] = 1;
C[0][0] = C[0][2] = C[1][1] = C[2][2] = 1;
mat_mul(C, A, 3, 3, 3, C);
ll ans = 1LL;
B[0][0] = 1; B[1][0] = B[2][0] = 0;
for(int x : V) {
mat_pow(C, 3, x - las - 1, T);
mat_mul(A, T, 3, 3, 3, T);
mat_mul(T, B, 3, 3, 1, B);
las = x;
}
printf("%lldn", B[2][0]);
return 0;
}
|
近期评论