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: 5.03 KB  |  hits: 11  |  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 mul2(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 (j < i) {
  54.                 c[i][j] = c[j][i];
  55.                 continue;
  56.             }
  57.             if (i > ROWS - i - 1) {
  58.                 c[i][j] = c[ROWS - i - 1][ROWS - j - 1];
  59.                 continue;
  60.             }
  61.             bb = b[j];
  62.             v = 0;
  63.             for (int k = 0; k < ROWS; k++) {
  64.                 if (aa[k] != 0 && bb[k] != 0) {
  65.                     v += (ulong) aa[k] * bb[k];    
  66.                     if (v >= MOD) {
  67.                         v %= MOD;
  68.                     }
  69.                 }
  70.             }
  71.             c[i][j] = (uint)v;
  72.         }
  73.     }    
  74. }
  75.  
  76. ulong go(ulong n) {
  77.     if (n == 1) {
  78.         return 10;
  79.     }
  80.     --n;
  81.     for (int i = 0; i < ROWS; i++) {
  82.         for (int j = 0; j < ROWS; j++) {
  83.             ans[i][j] = i == j ? 1 : 0;
  84.         }
  85.     }
  86.     for (int i = 0; i < 64; i += MANY) {
  87.         int t = n & (PMANY - 1);
  88.         if (t != 0) {
  89.             mul2(ans, tPows[i + 1][t], tmp);
  90.             Matrix e = ans;
  91.             ans = tmp;
  92.             tmp = e;
  93.         }
  94.         n >>= MANY;
  95.     }
  96.     ulong ret = 0;
  97.     for (int i = 1; i < ROWS; i++) {
  98.         ret += ans[i][i - 1];
  99.         if (ret >= MOD) {
  100.             ret -= MOD;
  101.         }
  102.         if (i < ROWS - 1) {
  103.             ret += ans[i][i + 1];
  104.             if (ret >= MOD) {
  105.                 ret -= MOD;
  106.             }
  107.         }
  108.     }
  109.     return ret;
  110. }
  111.  
  112. void mul(Matrix const & a, Matrix const & b, Matrix & c) {    
  113.     for (int i = 0; i < ROWS; i++) {
  114.         for (int j = 0; j < ROWS; j++) {
  115.             ulong v = 0;
  116.             for (int k = 0; k < ROWS; k++) {
  117.                 v += (ulong) a[i][k] * b[k][j];
  118.                 if (v >= MOD) {
  119.                     v %= MOD;
  120.                 }
  121.             }
  122.             c[i][j] = (uint)v;
  123.         }
  124.     }    
  125. }
  126.  
  127. void makeMatrix(Matrix & a) {
  128.     a = new uint*[ROWS];
  129.     for (int i = 0; i < ROWS; i++) {
  130.         a[i] = new uint[ROWS];
  131.         for (int j = 0; j < ROWS; j++) {
  132.             a[i][j] = 0;
  133.         }
  134.     }
  135. }
  136.  
  137. int main() {
  138.     freopen("in.txt", "r", stdin);
  139.     freopen("out.txt", "w", stdout);
  140.     pows = new Matrix[POW];
  141.     for (int i = 0; i < POW; i++) {
  142.         pows[i] = new uint*[ROWS];
  143.         for (int j = 0; j < ROWS; j++) {
  144.             pows[i][j] = new uint[ROWS];
  145.             for (int k = 0; k < ROWS; k++) {
  146.                 pows[i][j][k] = 0;
  147.             }
  148.         }
  149.     }
  150.     tmp = new uint*[ROWS];
  151.     ans = new uint*[ROWS];
  152.     for (int i = 0; i < ROWS; i++) {
  153.         tmp[i] = new uint[ROWS];
  154.         ans[i] = new uint[ROWS];
  155.     }
  156.     for (int i = 0; i < ROWS; i++) {
  157.         pows[0][i][i] = 1;
  158.     }
  159.     for (int i = 0; i < ROWS; i++) {
  160.         if (i > 0) {
  161.             pows[1][i][i - 1] = 1;
  162.         }
  163.         if (i < ROWS - 1) {
  164.             pows[1][i][i + 1] = 1;
  165.         }
  166.     }
  167.     for (int i = 2; i < POW; i++) {
  168.         mul2(pows[i - 1], pows[i - 1], pows[i]);
  169.     }
  170.     tPows = new Matrix*[POW];
  171.     for (int i = 1; i < POW; i += MANY) {
  172.         tPows[i] = new Matrix[PMANY];
  173.         for (int j = 0; j < PMANY; j++) {
  174.             bool ok = true;
  175.             for (int k = 0; k < MANY; k++) {
  176.                 if (((j >> k) & 1) == 1 && i + k > 64) {
  177.                     ok = false;
  178.                     break;
  179.                 }
  180.             }
  181.             if (!ok) {
  182.                 continue;
  183.             }
  184.             makeMatrix(tPows[i][j]);
  185.             Matrix & e = tPows[i][j];
  186.             for (int k = 0; k < ROWS; k++) {
  187.                 e[k][k] = 1;
  188.             }            
  189.             for (int k = 0; k < MANY; k++) {
  190.                 if (((j >> k) & 1) == 1) {
  191.                     mul2(e, pows[i + k], tmp);
  192.                     Matrix t = tmp;
  193.                     tmp = e;
  194.                     e = t;
  195.                 }
  196.             }
  197.         }
  198.     }
  199.     int n;
  200.     scanf("%d", &n);
  201.     for (int i = 0; i < n; i++) {
  202.         ulong x;
  203.         scanf("%lld", &x);
  204.         printf("%lld\n", go(x));
  205.     }
  206.     return 0;
  207. }
create a new version of this paste RAW Paste Data