fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n, k, q;
  5. int mod = 20191126;
  6. struct matrix{ //定義矩陣
  7.     int mat[6][6];
  8.     void reset(){
  9.         memset(mat, 0, sizeof(mat));
  10.     }
  11. };
  12. matrix mul(matrix a, matrix b){ //矩陣乘法
  13.     matrix c;
  14.     c.reset();
  15.     for(int i=0;i<6;i++){
  16.         for(int j=0;j<6;j++){
  17.             for(int k=0;k<6;k++){
  18.                 c.mat[i][j] += ((a.mat[i][k] % mod) * (b.mat[k][j] % mod) % mod);
  19.                 c.mat[i][j] %= mod;
  20.             }
  21.         }
  22.     }
  23.     return c;
  24. }
  25. matrix fpow(matrix a, int n){ //快速冪
  26.     matrix b;
  27.     b.reset();
  28.     for(int i=0;i<6;i++) b.mat[i][i] = 1;
  29.     while(n){
  30.         if(n % 2){
  31.             b = mul(b, a);
  32.         }
  33.         a = mul(a, a);
  34.         n /= 2;
  35.     }
  36.     return b;
  37. }
  38. signed main(){
  39.     ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  40.     cin>>q;
  41.     matrix A;
  42.     A.reset();
  43.     A.mat[1][0] = A.mat[0][1] = A.mat[1][1] = 1;
  44.     A.mat[0][2] = A.mat[1][2] = A.mat[2][2] = 1;
  45.     A.mat[0][3] = A.mat[1][3] = A.mat[2][3] = A.mat[3][3] = 1;
  46.     A.mat[0][4] = A.mat[1][4] = A.mat[2][4] = A.mat[3][4] = A.mat[4][4] = 1;
  47.     A.mat[0][5] = A.mat[1][5] = A.mat[2][5] = A.mat[3][5] = A.mat[4][5] =
  48.     A.mat[5][5] = 1;
  49.     while(q--){
  50.         cin>>k>>n;
  51.         /*for(int i=0;i<6;i++){
  52.             for(int j=0;j<6;j++) cout<<A.mat[j][i];
  53.             cout<<"\n";
  54.         }*/
  55.         int a[6] = {1, 1, 2, 3, 4, 5}, b[6] = {};
  56.         if(n - 2 <= 0){
  57.             if(n == 1) cout<<"1\n";
  58.             else {
  59.                 cout<<a[k+1]<<"\n";
  60.             }
  61.             continue;
  62.         }
  63.         matrix AA = fpow(A, n-2);
  64.         for(int i=0;i<6;i++){
  65.             for(int j=0;j<6;j++){
  66.                 b[i] += (AA.mat[j][i] * a[j]) % mod;
  67.                 b[i] %= mod;
  68.             }
  69.         }
  70. //        for(int i=0;i<6;i++) cout<<b[i]<<" ";
  71. //        cout<<"\n";
  72.         cout<<b[k+1]<<"\n";
  73.     }
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0.01s 5472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aTRSCn
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!