Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <cstring>
- using namespace std;
- #define MOD 1000000000
- struct matrix{
- int n;
- long long mat[6][6];
- matrix(){
- n = 6;
- memset(mat, 0, sizeof mat);
- }
- friend matrix operator * (const matrix &a, const matrix &b){
- matrix ret;
- for(int i = 0; i < a.n; ++i)
- for(int j = 0; j < a.n; ++j)
- for(int k = 0; k < a.n; ++k)
- ret.mat[i][j] = ((long long) ret.mat[i][j] + (long long) a.mat[i][k]*b.mat[k][j]) % MOD;
- return ret;
- }
- friend matrix operator ^ (const matrix &a, int pot){
- if(pot == 1) return a;
- if(pot & 1) return a * (a^(pot-1));
- matrix t = a^(pot >> 1);
- return t*t;
- }
- };
- long long pot_num(int base, int exp){
- if(exp == 0) return 1;
- if(exp & 1) return (long long) base*pot_num(base, exp-1) % MOD;
- long long t = pot_num(base, exp >> 1);
- return (long long) t*t % MOD;
- }
- long long calc3(int m){
- if(m & 1) return 0;
- return pot_num(2, (m >> 1)-1);
- }
- long long calc4(int m){
- if(m == 0 || m == 1) return 0;
- if(m == 2) return 1;
- if(m == 3) return 2;
- matrix t;
- t.mat[0][0] = 2, t.mat[0][1] = 2, t.mat[0][2] = -2, t.mat[0][3] = 1;
- t.mat[1][0] = 1;
- t.mat[2][1] = 1;
- t.mat[3][2] = 1;
- matrix a;
- a.mat[0][0] = 2;
- a.mat[1][0] = 1;
- a = (t^(m-3)) * a;
- return a.mat[0][0];
- }
- long long calc5(int m){
- if(m == 0 || m == 3 || m == 5) return 0;
- if(m == 2) return 1;
- if(m == 4) return 14;
- matrix t;
- t.mat[0][1] = 11, t.mat[0][5] = 2;
- t.mat[1][0] = 1;
- t.mat[2][1] = 1;
- t.mat[3][2] = 1;
- t.mat[4][3] = 1;
- t.mat[5][4] = 1;
- matrix a;
- a.mat[1][0] = 14;
- a.mat[3][0] = 1;
- a = (t^(m-5)) * a;
- return a.mat[0][0];
- }
- int n, m;
- int main(){
- scanf("%d%d", &n, &m);
- if(n == 2) printf("2\n");
- else if(n == 3) printf("%d\n", (2*calc3(m)) % MOD);
- else if(n == 4) printf("%d\n", (2*calc4(m)) % MOD);
- else printf("%d\n", (2*calc5(m)) % MOD);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement