YEZAELP

PROG-1134: Sequence

Oct 13th, 2021
810
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. const int mod = 2553;
  5. using lli = long long;
  6. int a, b, c, d, e, f, g, h;
  7. int ar[65][4][4];
  8. lli pow2[65];
  9.  
  10. int main(){
  11.  
  12.     scanf("%d%d%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f, &g, &h);
  13.  
  14.     ar[0][0][0] = e, ar[0][0][1] = f, ar[0][0][2] = g, ar[0][0][3] = h;
  15.     ar[0][1][0] = ar[0][2][1] = ar[0][3][2] = 1;
  16.     pow2[0] = 1;
  17.  
  18.     for(int idx=1;idx<=60;idx++){
  19.         pow2[idx] = (lli) pow2[idx-1] * 2;
  20.         for(int i=0;i<4;i++){
  21.             for(int j=0;j<4;j++){
  22.                 ar[idx][i][j] = 0;
  23.                 for(int k=0;k<4;k++){
  24.                     ar[idx][i][j] += (ar[idx-1][i][k] * ar[idx-1][k][j]) % mod;
  25.                     ar[idx][i][j] %= mod;
  26.                 }
  27.             }
  28.         }
  29.     }
  30.  
  31.     int q;
  32.     scanf("%d", &q);
  33.  
  34.     while(q --){
  35.         lli n;
  36.         scanf("%lld", &n);
  37.         if(n == 1) printf("%d\n", a);
  38.         else if(n == 2) printf("%d\n", b);
  39.         else if(n == 3) printf("%d\n", c);
  40.         else if(n == 4) printf("%d\n", d);
  41.         else{
  42.             int ans[4] = {d, c, b, a};
  43.             n -= 4;
  44.             for(int idx=0;idx<=60;idx++){
  45.                 if(pow2[idx] & n){
  46.                     int keep[4];
  47.                     keep[0] = ( ar[idx][0][0] * ans[0] + ar[idx][0][1] * ans[1] + ar[idx][0][2] * ans[2] + ar[idx][0][3] * ans[3]) % mod;
  48.                     keep[1] = ( ar[idx][1][0] * ans[0] + ar[idx][1][1] * ans[1] + ar[idx][1][2] * ans[2] + ar[idx][1][3] * ans[3]) % mod;
  49.                     keep[2] = ( ar[idx][2][0] * ans[0] + ar[idx][2][1] * ans[1] + ar[idx][2][2] * ans[2] + ar[idx][2][3] * ans[3]) % mod;
  50.                     keep[3] = ( ar[idx][3][0] * ans[0] + ar[idx][3][1] * ans[1] + ar[idx][3][2] * ans[2] + ar[idx][3][3] * ans[3]) % mod;
  51.                     for(int i=0;i<4;i++)
  52.                         ans[i] = keep[i];
  53.                 }
  54.             }
  55.             printf("%d\n", ans[0]);
  56.         }
  57.     }
  58.  
  59.     return 0;
  60. }
  61.  
RAW Paste Data