Advertisement
Guest User

Untitled

a guest
Aug 12th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement