Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 8th, 2012  |  syntax: None  |  size: 7.81 KB  |  hits: 20  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <stdio.h>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. typedef unsigned long long ulong;
  7. typedef unsigned int uint;
  8. typedef uint** Matrix;
  9.  
  10. const ulong MOD = 4294967143LL;
  11. const int ROWS = 11;
  12. const int POW = 65;
  13. const int MANY = 8;
  14. const int PMANY = 1 << MANY;
  15. /*class Matrix {
  16.     public:
  17.     int n;
  18.     ulong ** a;
  19.  
  20.     Matrix(int n_ = ROWS) : n(n_) {        
  21.         a = new ulong*[n];
  22.         for (int i = 0; i < n; i++) {
  23.             a[i] = new ulong[n];
  24.             for (int j = 0; j < n; j++) {
  25.                 a[i][j] = 0;
  26.             }
  27.         }
  28.     }
  29.  
  30.     ulong * operator[] (size_t x) {
  31.         return a[x];
  32.     }
  33.  
  34.     ulong * operator[] (size_t x) const {
  35.         return a[x];
  36.     }
  37. };*/
  38.  
  39. Matrix * pows;
  40. Matrix ** tPows;
  41. Matrix tmp;
  42. Matrix ans;
  43.  
  44. void mul(Matrix const & a, Matrix const & b, Matrix & c);
  45.  
  46. void mul3(Matrix const & a, Matrix const & b, Matrix & c) {
  47.     uint * aa;
  48.     uint * bb;
  49.     ulong v;
  50.     for (int i = 0; i < ROWS; i++) {
  51.         aa = a[i];
  52.         for (int j = 0; j < ROWS; j++) {
  53.             if (((i + j) & 1) == 0) {
  54.                 c[i][j] = 0;
  55.                 continue;
  56.             }
  57.             if (j < i) {
  58.                 c[i][j] = c[j][i];
  59.                 continue;
  60.             }
  61.             if (i > ROWS - i - 1) {
  62.                 c[i][j] = c[ROWS - i - 1][ROWS - j - 1];
  63.                 continue;
  64.             }
  65.             if (j > ROWS - i - 1) {
  66.                 c[i][j] = c[ROWS - j - 1][ROWS - i - 1];
  67.                 continue;
  68.             }
  69.             bb = b[j];
  70.             v = 0;
  71.             for (int k = 0; k < ROWS; k++) {
  72.                 if (aa[k] != 0 && bb[k] != 0) {
  73.                     v += (ulong) aa[k] * (ulong) bb[k];
  74.                     if (v >= MOD) {
  75.                         v %= MOD;
  76.                     }
  77.                 }
  78.             }
  79.             c[i][j] = (uint)v;
  80.         }
  81.     }    
  82. }
  83.  
  84. void mul4(Matrix const & a, Matrix const & b, Matrix & c) {
  85.     uint * aa;
  86.     uint * bb;
  87.     ulong v;
  88.     for (int i = 0; i < ROWS; i++) {
  89.         aa = a[i];
  90.         for (int j = 0; j < ROWS; j++) {
  91.             if (((i + j) & 1) == 1) {
  92.                 c[i][j] = 0;
  93.                 continue;
  94.             }
  95.             if (j < i) {
  96.                 c[i][j] = c[j][i];
  97.                 continue;
  98.             }
  99.             if (i > ROWS - i - 1) {
  100.                 c[i][j] = c[ROWS - i - 1][ROWS - j - 1];
  101.                 continue;
  102.             }
  103.             if (j > ROWS - i - 1) {
  104.                 c[i][j] = c[ROWS - j - 1][ROWS - i - 1];
  105.                 continue;
  106.             }
  107.             bb = b[j];
  108.             v = 0;
  109.             for (int k = 0; k < ROWS; k++) {
  110.                 if (aa[k] != 0 && bb[k] != 0) {
  111.                     v += (ulong) aa[k] * (ulong) bb[k];
  112.                     if (v >= MOD) {
  113.                         v %= MOD;
  114.                     }
  115.                 }
  116.             }
  117.             c[i][j] = (uint)v;
  118.         }
  119.     }    
  120. }
  121.  
  122. void mul2(Matrix const & a, Matrix const & b, Matrix & c) {    
  123.     uint * aa;
  124.     uint * bb;
  125.     ulong v;    
  126.     for (int i = 0; i < ROWS; i++) {
  127.         aa = a[i];
  128.         for (int j = 0; j < ROWS; j++) {            
  129.             if (j < i) {
  130.                 c[i][j] = c[j][i];
  131.                 continue;
  132.             }
  133.             if (i > ROWS - i - 1) {
  134.                 c[i][j] = c[ROWS - i - 1][ROWS - j - 1];
  135.                 continue;
  136.             }
  137.             if (j > ROWS - i - 1) {
  138.                 c[i][j] = c[ROWS - j - 1][ROWS - i - 1];
  139.                 continue;
  140.             }
  141.             bb = b[j];
  142.             v = 0;
  143.             for (int k = 0; k < ROWS; k++) {
  144.                 if (aa[k] != 0 && bb[k] != 0) {
  145.                     v += (ulong) aa[k] * (ulong) bb[k];
  146.                     if (v >= MOD) {
  147.                         v %= MOD;
  148.                     }
  149.                 }
  150.             }
  151.             c[i][j] = (uint)v;
  152.         }
  153.     }    
  154. }
  155.  
  156. ulong go(ulong n) {
  157.     if (n == 1) {
  158.         return 10;
  159.     }
  160.     if ((n & 1) == 1) {
  161.         return 0;
  162.     }
  163.     --n;
  164.     for (int i = 0; i < ROWS; i++) {
  165.         for (int j = 0; j < ROWS; j++) {
  166.             ans[i][j] = i == j ? 1 : 0;
  167.         }
  168.     }
  169. //    bool ok = (n & 1) == 0;
  170.     for (int i = 0; i < 64; i += MANY) {
  171.         int t = n & (PMANY - 1);
  172.         if (t != 0) {
  173. //            if (ok)
  174. //                mul4(ans, tPows[i + 1][t], tmp);
  175.                //mul2(ans, tPows[i + 1][t], tmp);
  176. //            else
  177.                 mul3(ans, tPows[i + 1][t], tmp);
  178.                //mul2(ans, tPows[i + 1][t], tmp);
  179.             Matrix e = ans;
  180.             ans = tmp;
  181.             tmp = e;
  182.         }
  183.         n >>= MANY;
  184.     }
  185.     ulong ret = 0;
  186.     for (int i = 1; i < ROWS; i++) {
  187.         ret += ans[i][i - 1];
  188.         if (ret >= MOD) {
  189.             ret -= MOD;
  190.         }
  191.         if (i < ROWS - 1) {
  192.             ret += ans[i][i + 1];
  193.             if (ret >= MOD) {
  194.                 ret -= MOD;
  195.             }
  196.         }
  197.     }
  198.     return ret;
  199. }
  200.  
  201. void mul(Matrix const & a, Matrix const & b, Matrix & c) {    
  202.     for (int i = 0; i < ROWS; i++) {
  203.         for (int j = 0; j < ROWS; j++) {
  204.             ulong v = 0;
  205.             for (int k = 0; k < ROWS; k++) {
  206.                 v += (ulong) a[i][k] * b[k][j];
  207.                 if (v >= MOD) {
  208.                     v %= MOD;
  209.                 }
  210.             }
  211.             c[i][j] = (uint)v;
  212.         }
  213.     }    
  214. }
  215.  
  216. void makeMatrix(Matrix & a) {
  217.     a = new uint*[ROWS];
  218.     for (int i = 0; i < ROWS; i++) {
  219.         a[i] = new uint[ROWS];
  220.         for (int j = 0; j < ROWS; j++) {
  221.             a[i][j] = 0;
  222.         }
  223.     }
  224. }
  225.  
  226. int main() {
  227.     freopen("in.txt", "r", stdin);
  228.     freopen("out.txt", "w", stdout);
  229.     pows = new Matrix[POW];
  230.     for (int i = 0; i < POW; i++) {
  231.         makeMatrix(pows[i]);
  232.     }
  233.     makeMatrix(tmp);
  234.     makeMatrix(ans);
  235.     for (int i = 0; i < ROWS; i++) {
  236.         pows[0][i][i] = 1;
  237.     }
  238.     for (int i = 0; i < ROWS; i++) {
  239.         if (i > 0) {
  240.             pows[1][i][i - 1] = 1;
  241.         }
  242.         if (i < ROWS - 1) {
  243.             pows[1][i][i + 1] = 1;
  244.         }
  245.     }
  246.     for (int i = 2; i < POW; i++) {
  247. //       if (i == 2)
  248. //            mul2(pows[i - 1], pows[i - 1], pows[i]);
  249. //        else
  250.             mul4(pows[i - 1], pows[i - 1], pows[i]);            
  251.     }
  252.     tPows = new Matrix*[POW];
  253.     for (int i = 1; i < POW; i += MANY) {
  254.         tPows[i] = new Matrix[PMANY];
  255.         for (int j = 0; j < PMANY; j++) {            
  256.             bool ok = true;
  257.             for (int k = 0; k < MANY; k++) {
  258.                 if (((j >> k) & 1) == 1 && i + k > 64) {
  259.                     ok = false;
  260.                     break;
  261.                 }
  262.             }
  263.             if (!ok) {
  264.                 continue;
  265.             }
  266.             if (i == 1 && j != 0 && (j & 1) == 0) {
  267.                 continue;
  268.             }
  269.             makeMatrix(tPows[i][j]);
  270.             Matrix & e = tPows[i][j];
  271.             if (j == 0) {
  272.                 for (int k = 0; k < ROWS; k++) {
  273.                     e[k][k] = 1;
  274.                 }
  275.                 continue;
  276.             }
  277.             for (int k = MANY - 1; k >= 0; k--) {
  278.                 if (((j >> k) & 1) == 1) {
  279.                     if (i == 1 && (j & 1) == 1) {
  280.                         mul3(pows[i + k], tPows[i][j ^ (1 << k)], e);
  281.                         //mul2(pows[i + k], tPows[i][j ^ (1 << k)], e);
  282.                     } else {
  283.                         mul4(pows[i + k], tPows[i][j ^ (1 << k)], e);
  284.                         //mul2(pows[i + k], tPows[i][j ^ (1 << k)], e);
  285.                     }
  286.                     break;
  287.                 }
  288.             }
  289.         }
  290.     }
  291.     int n;
  292.     scanf("%d", &n);
  293.     for (int i = 0; i < n; i++) {
  294.         ulong x;
  295.         scanf("%lld", &x);
  296.         printf("%lld\n", go(x));
  297.     }
  298.     return 0;
  299. }
create a new version of this paste RAW Paste Data