• API
• FAQ
• Tools
• Archive
daily pastebin goal
23%
SHARE
TWEET

Untitled

a guest Aug 12th, 2017 47 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <cstdio>
3. #include <vector>
4. #include <cstring>
5. using namespace std;
6. #define MOD 1000000000
7.
8. struct matrix{
9.   int n;
10.   long long mat[6][6];
11.
12.   matrix(){
13.     n = 6;
14.     memset(mat, 0, sizeof mat);
15.   }
16.
17.   friend matrix operator * (const matrix &a, const matrix &b){
18.     matrix ret;
19.     for(int i = 0; i < a.n; ++i)
20.       for(int j = 0; j < a.n; ++j)
21.         for(int k = 0; k < a.n; ++k)
22.           ret.mat[i][j] = ((long long) ret.mat[i][j] + (long long) a.mat[i][k]*b.mat[k][j]) % MOD;
23.     return ret;
24.   }
25.
26.   friend matrix operator ^ (const matrix &a, int pot){
27.     if(pot == 1) return a;
28.     if(pot  & 1) return a * (a^(pot-1));
29.     matrix t = a^(pot >> 1);
30.     return t*t;
31.   }
32. };
33.
34. long long pot_num(int base, int exp){
35.   if(exp == 0) return 1;
36.   if(exp & 1) return (long long) base*pot_num(base, exp-1) % MOD;
37.   long long t = pot_num(base, exp >> 1);
38.   return (long long) t*t % MOD;
39. }
40.
41. long long calc3(int m){
42.   if(m & 1) return 0;
43.   return pot_num(2, (m >> 1)-1);
44. }
45.
46. long long calc4(int m){
47.   if(m == 0 || m == 1) return 0;
48.   if(m == 2) return 1;
49.   if(m == 3) return 2;
50.
51.   matrix t;
52.   t.mat[0][0] = 2, t.mat[0][1] = 2, t.mat[0][2] = -2, t.mat[0][3] = 1;
53.   t.mat[1][0] = 1;
54.   t.mat[2][1] = 1;
55.   t.mat[3][2] = 1;
56.
57.   matrix a;
58.   a.mat[0][0] = 2;
59.   a.mat[1][0] = 1;
60.
61.   a = (t^(m-3)) * a;
62.   return a.mat[0][0];
63. }
64.
65. long long calc5(int m){
66.   if(m == 0 || m == 3 || m == 5) return 0;
67.   if(m == 2) return 1;
68.   if(m == 4) return 14;
69.
70.   matrix t;
71.   t.mat[0][1] = 11, t.mat[0][5] = 2;
72.   t.mat[1][0] = 1;
73.   t.mat[2][1] = 1;
74.   t.mat[3][2] = 1;
75.   t.mat[4][3] = 1;
76.   t.mat[5][4] = 1;
77.
78.   matrix a;
79.   a.mat[1][0] = 14;
80.   a.mat[3][0] = 1;
81.
82.   a = (t^(m-5)) * a;
83.   return a.mat[0][0];
84. }
85.
86. int n, m;
87.
88. int main(){
89.   scanf("%d%d", &n, &m);
90.   if(n == 2) printf("2\n");
91.   else if(n == 3) printf("%d\n", (2*calc3(m)) % MOD);
92.   else if(n == 4) printf("%d\n", (2*calc4(m)) % MOD);
93.   else printf("%d\n", (2*calc5(m)) % MOD);
94.   return 0;
95. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top