fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll kq = 0,k,n,tam;
  5. const ll mod = 1000;
  6. struct matrix
  7. {
  8.     ll mx[4][4];
  9. }a,b;
  10. matrix nhan(matrix a, matrix b, ll m)
  11. {
  12.     matrix c;
  13.     for(int i = 1; i <= m; i++)
  14.     {
  15.         for(int j = 1; j <= 3; j++)
  16.         {
  17.             c.mx[i][j] = 0;
  18.             for(int k = 1; k <= 3; k++)
  19.             {
  20.                 c.mx[i][j] = (c.mx[i][j] + a.mx[i][k]*b.mx[k][j])%mod;
  21.             }
  22.         }
  23.     }
  24.     return c;
  25. }
  26. matrix mu(matrix a, ll b)
  27. {
  28.     if(b == 1)
  29.         return a;
  30.     matrix tam = mu(a,b/2);
  31.     tam = nhan(tam,tam,3);
  32.     if(b%2 == 1)
  33.         return nhan(tam,a,3);
  34.     return tam;
  35. }
  36. int main()
  37. {
  38.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  39.     freopen("DAYSO.inp", "r", stdin);
  40.     freopen("DAYSO.out", "w", stdout);
  41.     cin >> k;
  42.     while(k--)
  43.     {
  44.         cin >> n;
  45.         a.mx[1][1] = 1, a.mx[1][2] = 0,a.mx[1][3] = 1;
  46.         b.mx[1][1] = 2;
  47.         b.mx[2][1] = -1;
  48.         b.mx[3][1] = 1;
  49.         b.mx[1][2] = 1;
  50.         b.mx[2][2] = 0;
  51.         b.mx[3][2] = 0;
  52.         b.mx[1][3] = 0;
  53.         b.mx[2][3] = 0;
  54.         b.mx[3][3] = 1;
  55.         b = mu(b,n);
  56.         a = nhan(a,b,1);
  57.         tam =  a.mx[1][1] - a.mx[1][2];
  58.         tam*=tam;
  59.         tam%=10;
  60.         cout << tam << '\n';
  61.     }
  62. }
  63.  
  64.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vADyuh
language:
C++14 (gcc 8.3)
created:
81 days 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!