oj.uz

Submission #9715

# Submission time Handle Problem Language Result Execution time Memory
9715 2014-09-28T08:19:47 Z jaehadad On grid (kriii2_O) C++14
0 / 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;
  }
  // [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
0.0 / 1.0

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

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -