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
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod = 1e3;
int n, A[8][8], B[8][8], C[8][8];
int main ()
{
for (int i = 0; i < 8; i++)
A[i][i] = 1;
for (int i = 0; i < 7; i++)
B[i][(i + 1) % 8] = B[i][(i + 7) % 8] = 1;
cin >> n;
while (n)
{
if (n & 1)
{
memset(C, 0, sizeof C);
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
for (int k = 0; k < 8; k++)
C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % mod) % mod;
memcpy(A, C, sizeof A);
}
memset(C, 0, sizeof C);
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
for (int k = 0; k < 8; k++)
C[i][j] = (C[i][j] + (B[i][k] * B[k][j]) % mod) % mod;
memcpy(B, C, sizeof B);
n >>= 1;
}
int res = 0;
cout << A[3][7];
return 0;
}
|