Advertisement
YEZAELP

TUMSO18-K: Treasure

Dec 25th, 2021
970
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli Mod = 98765431;
  6. const int logN = 60;
  7. lli mat11[logN + 5], mat12[logN + 5], mat21[logN + 5], mat22[logN + 5], pw[logN + 5];
  8.  
  9. int main(){
  10.  
  11.     mat12[0] = 2, mat11[0] = mat22[0] = mat21[0] = 1;
  12.  
  13.     for(int i=1;i<=logN;i++){
  14.         mat11[i] = ( (mat11[i - 1] * mat11[i - 1]) % Mod + (mat12[i - 1] * mat21[i - 1]) % Mod ) % Mod;
  15.         mat12[i] = ( (mat11[i - 1] * mat12[i - 1]) % Mod + (mat12[i - 1] * mat22[i - 1]) % Mod ) % Mod;
  16.         mat21[i] = ( (mat21[i - 1] * mat11[i - 1]) % Mod + (mat22[i - 1] * mat21[i - 1]) % Mod ) % Mod;
  17.         mat22[i] = ( (mat21[i - 1] * mat12[i - 1]) % Mod + (mat22[i - 1] * mat22[i - 1]) % Mod ) % Mod;
  18.     }
  19.  
  20.     pw[0] = 1;
  21.     for(int i=1;i<=logN;i++)
  22.         pw[i] = (2 * pw[i - 1]);
  23.  
  24.     int Q;
  25.     scanf("%d", &Q);
  26.  
  27.     for(int q=1;q<=Q;q++){
  28.         lli n;
  29.         scanf("%lld", &n);
  30.  
  31.         lli one = 1, two = 1;
  32.         for(lli i=0;i<=logN;i++){
  33.             if(pw[i] & n){
  34.                 lli cur_one = ( (mat21[i] * two) % Mod + (mat22[i] * one) % Mod ) % Mod;
  35.                 lli cur_two = ( (mat11[i] * two) % Mod + (mat12[i] * one) % Mod ) % Mod;
  36.                 one = cur_one, two = cur_two;
  37.             }
  38.         }
  39.  
  40.         printf("%lld\n", two);
  41.     }
  42.  
  43.     return 0;
  44. }
Advertisement
RAW Paste Data Copied
Advertisement