結果

問題 No.344 ある無理数の累乗
コンテスト
ユーザー asi1024
提出日時 2016-02-19 21:08:53
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,488 bytes
コンパイル時間 1,579 ms
コンパイル使用メモリ 165,344 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 12:22:17
合計ジャッジ時間 2,487 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

const int mod = 1000;

struct Mod {
  int n;
  Mod () : n(0) {;}
  Mod (int n) : n(n) {
    if (n >= mod) n %= mod;
    else if (n < mod) n = (n % mod + mod) % mod;
  }
  operator int() { return n; }
};

Mod operator+=(Mod &a, Mod b) { a.n += b.n; if (a.n >= mod) a.n -= mod; return a; }
Mod operator-=(Mod &a, Mod b) { a.n -= b.n; if (a.n < 0) a.n += mod; return a; }
Mod operator*=(Mod &a, Mod b) { a.n = ((long long)a.n * b.n) % mod; return a; }
Mod operator+(Mod a, Mod b) { return a += b; }
Mod operator-(Mod a, Mod b) { return a -= b; }
Mod operator*(Mod a, Mod b) { return a *= b; }

typedef Mod Data;
typedef vector<Data> Array;
typedef vector<Array> Matrix;

Matrix operator*(const Matrix &lhs, const Matrix &rhs) {
  Matrix res(lhs.size(), Array(rhs[0].size(), 0));
  REP(i,lhs.size()) REP(j,rhs[0].size()) REP(k,rhs.size())
    res[i][j] += lhs[i][k] * rhs[k][j];
  return res;
}

Matrix scalar(int size, Data k) {
  Matrix mat(size, Array(size, 0));
  REP(i,size) mat[i][i] = k;
  return mat;
}

Matrix operator^(const Matrix &lhs, const int n) {
  if (n == 0) return scalar(lhs.size(), 1);
  Matrix res = (lhs * lhs) ^ (n / 2);
  if (n % 2) res = res * lhs;
  return res;
}

int main() {
  int n; cin >> n;
  Matrix mat = {{1, 3}, {1, 1}};
  mat = mat ^ n;
  Mod res = mat[0][0];
  cout << res * Mod(2) - Mod(1 - n % 2) << endl;
  return 0;
}
0