結果

問題 No.675 ドットちゃんたち
コンテスト
ユーザー Kutimoti_T
提出日時 2018-05-14 17:23:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 252 ms / 2,000 ms
コード長 2,383 bytes
コンパイル時間 1,456 ms
コンパイル使用メモリ 167,268 KB
実行使用メモリ 23,536 KB
最終ジャッジ日時 2024-06-28 11:46:11
合計ジャッジ時間 5,113 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#include <iostream>
#include <vector>
using namespace std;

#define int long long

template <class T>
struct Matrix {
  vector<vector<T>> value;
  T init;

  Matrix(vector<vector<T>> vec, T init_) : init(init_), value(vec) {}
  Matrix(int h, int w, T init_) : init(init_), value(h, vector<T>(w, init_)) {}

  Matrix<T> operator*(Matrix<T>& left) {
    Matrix<T> res(value.size(), left[0].size(), init);
    for (int i = 0; i < value.size(); i++) {
      for (int k = 0; k < left.size(); k++) {
        for (int j = 0; j < left[0].size(); j++) {
          res[i][j] = (res[i][j] + value[i][k] * left[k][j]);
        }
      }
    }
    return res;
  }

  Matrix<T> operator+(Matrix<T>& left) {
    Matrix<T> res = *this;
    for (int i = 0; i < res.size(); i++) {
      for (int j = 0; j < res[0].size(); j++) {
        res[i][j] += left[i][j];
      }
    }
    return res;
  }

  Matrix<T> operator*(T c) {
    Matrix<T> res = *this;
    for (int i = 0; i < res.size(); i++) {
      for (int j = 0; j < res[0].size(); j++) {
        res[i][j] *= c;
      }
    }
    return res;
  }

  vector<T>& operator[](int n) { return value[n]; }

  size_t size() { return value.size(); }

  Matrix<T> operator^(long long n) {
    Matrix<T> a = *this;
    Matrix<T> res(a.size(), a.size(), init);
    for (int i = 0; i < a.size(); i++) {
      res[i][i] = 1;
    }

    while (n > 0) {
      if (n & 1) res = res * a;
      a = a * a;
      n >>= 1;
    }
    return res;
  }
};

int N;
int Px;
int Py;

signed main(){
    cin >> N >> Px >> Py;

    Matrix<int> base(3,3,0);
    base[0][0] = base[1][1] = base[2][2] = 1;
    vector<Matrix<int>> m(N + 1,base);

    rep(i,0,N - 1){
        int c;
        int d;
        cin >> c;
        if(c == 1){
            cin >> d;
            m[i][0][2] = d;
        }
        if(c == 2){
            cin >> d;
            m[i][1][2] = d;
        }
        if(c == 3){
            m[i][0][0] = m[i][1][1] = 0;
            m[i][0][1] = 1;
            m[i][1][0] = -1;
        }
    }

    for(int i = N - 1;i >= 0;i--){
        m[i] = m[i + 1] * m[i];
    }
    Matrix<int> res(3,1,0);
    res[0][0] = Px;
    res[1][0] = Py;
    res[2][0] = 1;
    rep(i,0,N - 1){
        auto a = m[i] * res;
        cout << a[0][0] << " " << a[1][0] << endl;
    }
}
0