fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define matrix vector<vector<ll>>
  5. using namespace std;
  6. const int base=trunc(1e9)+7;
  7. matrix a,b;
  8. matrix operator * (const matrix &a, const matrix &b) {
  9.     matrix c = {{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}};
  10.     for (int i = 0; i <=4; i++) {
  11.         for (int j = 0; j <=4; j++) {
  12.             for (int k = 0; k <=4; k++) {
  13.                 c[i][j] = (c[i][j] + (a[i][k] * b[k][j]) % base) % base;
  14.             }
  15.         }
  16.     }
  17.     return c;
  18. }
  19. matrix mu(ll n) {
  20.     if (n == 1) return a;
  21.     matrix t = mu(n / 2);
  22.     t = t * t;
  23.     if (n % 2 == 1) t = t * a;
  24.     return t;
  25. }
  26. int main()
  27. {
  28.     ll n,a1,b1,c1,d1,e1;
  29.     cin>>n>>a1>>b1>>c1>>d1>>e1;
  30.     a=  {{0,0,c1,0,0},{1,0,b1,0,0},{0,1,a1,0,0},{0,0,d1,1,0},{0,0,e1,1,1}};
  31.     b=  {{1,1,1,4,1},{0,0,0,0,0},{ 0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}};
  32.     matrix d=mu(n-3);
  33.     matrix d2=b*d;
  34.     cout<<d2[0][2]% base;
  35.     return 0;
  36. }
Time limit exceeded #stdin #stdout 5s 2760704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DySI1D
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 years ago
visibility:
secret

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!