fork download
copy 
  1. #include <assert.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <time.h>
  6.  
  7. const int MSZ = 3;
  8.  
  9. struct Mat {
  10.   int d[MSZ][MSZ];
  11.  
  12.   Mat() {
  13.     memset(d, 0, sizeof d);
  14.     for (int i = 0; i < MSZ; i++)
  15.       d[i][i] = 1;
  16.   }
  17.  
  18.   void operator*=(const Mat &m2) {
  19.     int res[MSZ][MSZ];
  20.     memset(res, 0, sizeof res);
  21.     for (int i = 0; i < MSZ; i++)
  22.     for (int j = 0; j < MSZ; j++)
  23.     for (int k = 0; k < MSZ; k++)
  24.       res[i][j] += d[i][k] * m2.d[k][j];
  25.     memcpy(d, res, sizeof d);
  26.   }
  27. };
  28.  
  29. Mat pow1(Mat a, int b) {
  30.   Mat res;
  31.   for (; b; b >>= 1, a *= a)
  32.     if (b & 1) res *= a;
  33.   return res;
  34. }
  35.  
  36. Mat pow2(const Mat &a, int b) {
  37.     if (b == 0) {
  38.         return Mat();
  39.     }
  40.     Mat res = pow2(a, b >> 1);
  41.     res *= res;
  42.     if (b & 1) {
  43.         res *= a;
  44.     }
  45.     return res;
  46. }
  47.  
  48. const int POW = (1 << 30) - 1;
  49. const int STEPS = 3e5;
  50.  
  51. int main() {
  52.   Mat src;
  53.   for (int i = 0; i < MSZ; i++)
  54.   for (int j = 0; j < MSZ - i; j++)
  55.     src.d[i][j] = 1;
  56.  
  57.   Mat res;
  58.   clock_t st = clock();
  59.   for (int step = 0; step < STEPS; step++)
  60.     res = pow1(src, POW);
  61.   printf("%d\n", clock() - st);
  62.  
  63.   st = clock();
  64.   Mat res2;
  65.   for (int step = 0; step < STEPS; step++)
  66.     res2 = pow2(src, POW);
  67.   printf("%d\n", clock() - st);
  68.  
  69.   for (int i = 0; i < MSZ; i++)
  70.   for (int j = 0; j < MSZ; j++)
  71.     assert(res.d[i][j] == res2.d[i][j]);
  72.   return 0;
  73. }
  74.  
Success #stdin #stdout 2.4s 2680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
910000
1470000
https://ideone.com/Xguv8
language:
C++ (gcc 8.3)
created:
11 years 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!