oj.uz

Submission #9720

# Submission time Handle Problem Language Result Execution time Memory
9720 2014-09-28T08:21:14 Z jaehadad Phibonacci (kriii2_P) C++14
1 / 4
 0 ms 1676 KB 
#include<cstdio>
#include<cassert>
#include<cstring>
#include<map>
#include<set>
#include<time.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

typedef vector<vector<long long> > Matrix;
const int MOD = 1000 * 1000 * 1000 + 7;

Matrix operator * (const Matrix& a, const Matrix& b) {
  int n = a.size();
  Matrix ret(n, vector<long long>(n));
  for(int k = 0; k < n; ++k)
    for(int i = 0; i < n; ++i)
      for(int j = 0; j < n; ++j)
        ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % MOD;
  return ret;
}

Matrix eye(int n) {
  Matrix ret(n, vector<long long>(n));
  for(int i = 0; i < n; ++i)
    ret[i][i] = 1;
  return ret;
}

Matrix pow(const Matrix& a, long long n) {
  Matrix ret = eye(a.size());
  Matrix unit = a;
  for(int i = 0; (1ll << i) <= n; ++i) {
    if(n & (1ll << i))
      ret = ret * unit;
    unit = unit * unit;
  }
  return ret;
}

int main() {

  long long n, k;
  cin >> n >> k;

  if(n == 0) {
    cout << "0 1" << endl;
    return 0;
  }
  // [0 1][f(0)] = [f(1)]
  // [1 1][f(1]] = [f(2)]
  Matrix m(2, vector<long long>(2, 1));
  m[0][0] = 0;

  Matrix mp = pow(m, n-1);
  cout << mp[1][1] << ' ' << mp[0][1] << endl;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1676 KB Output is correct
2 Correct 0 ms 1676 KB Output is correct
3 Correct 0 ms 1676 KB Output is correct
4 Correct 0 ms 1676 KB Output is correct
5 Correct 0 ms 1676 KB Output is correct
6 Correct 0 ms 1676 KB Output is correct
7 Correct 0 ms 1676 KB Output is correct
8 Correct 0 ms 1676 KB Output is correct
9 Correct 0 ms 1676 KB Output is correct
10 Correct 0 ms 1676 KB Output is correct
11 Correct 0 ms 1676 KB Output is correct
12 Correct 0 ms 1676 KB Output is correct
13 Correct 0 ms 1676 KB Output is correct
14 Correct 0 ms 1676 KB Output is correct
15 Correct 0 ms 1676 KB Output is correct
16 Correct 0 ms 1676 KB Output is correct
17 Correct 0 ms 1676 KB Output is correct
18 Correct 0 ms 1676 KB Output is correct
19 Correct 0 ms 1676 KB Output is correct
20 Correct 0 ms 1676 KB Output is correct

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1676 KB Output isn't correct
2 Halted 0 ms 0 KB -