Submission #9719

#	Time	Username	Problem	Language	Result	Execution time	Memory
9719		jaehadad	On grid (kriii2_O)	C++14	0 / 4	0 ms	1676 KiB

O

#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: 0 / 1
• Subtask 2: 0 / 3