結果
| 問題 | No.2441 行列累乗 |
| ユーザー |
 marc2825
|
| 提出日時 | 2023-08-25 21:22:38 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 14,770 bytes |
| コンパイル時間 | 2,204 ms |
| コンパイル使用メモリ | 155,304 KB |
| 実行使用メモリ | 4,384 KB |
| 最終ジャッジ日時 | 2023-08-25 21:22:41 |
| 合計ジャッジ時間 | 2,842 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,380 KB |
| testcase_01 | AC | 2 ms
4,380 KB |
| testcase_02 | AC | 2 ms
4,376 KB |
| testcase_03 | AC | 2 ms
4,376 KB |
| testcase_04 | AC | 2 ms
4,380 KB |
| testcase_05 | AC | 2 ms
4,380 KB |
| testcase_06 | AC | 1 ms
4,376 KB |
| testcase_07 | AC | 2 ms
4,384 KB |
| testcase_08 | AC | 1 ms
4,376 KB |
| testcase_09 | AC | 2 ms
4,380 KB |
| testcase_10 | AC | 2 ms
4,376 KB |
| testcase_11 | AC | 1 ms
4,380 KB |
| testcase_12 | AC | 1 ms
4,380 KB |
| testcase_13 | AC | 2 ms
4,380 KB |
| testcase_14 | AC | 1 ms
4,380 KB |
| testcase_15 | AC | 2 ms
4,380 KB |
| testcase_16 | AC | 1 ms
4,380 KB |
| testcase_17 | AC | 2 ms
4,380 KB |
| testcase_18 | AC | 1 ms
4,380 KB |
| testcase_19 | AC | 2 ms
4,384 KB |
ソースコード
//#pragma GCC target ("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #ifndef ONLINE_JUDGE
// #define _GLIBCXX_DEBUG
// #endif
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <string>
#include <bitset>
#include <functional>
#include <list>
#include <deque>
#include <utility>
#include <numeric>
#include <complex>
#include <cctype>
#include <limits>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <random>
#include <fstream>
#include <chrono>
//#include <bit>
//#include <regex>
//#include <cstdio>
//#include <atcoder/all>
//using namespace atcoder;
using namespace std;
//#define int long long
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ld = long double;
using vld = vector<ld>;
using vd = vector<double>;
using vvd = vector<vd>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pii = pair<int, int>;
using pcc = pair<char, char>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using pldld = pair<ld,ld>;
using vpii = vector<pii>;
using vpll = vector<pll>;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
#define rep(i, n) for (ll i = 0; i < ll(n); i++)
#define repback(i, n) for (ll i = n-1; i >= 0; i--)
#define REP(i, a, b) for (ll i = a; i < ll(b); i++)
#define REPBACK(i, a, b) for (ll i = a-1; i >= ll(b); i--)
#define all(x) (x).begin(), (x).end()
#define UNIQUE(A) A.erase(unique(all(A)), A.end()) // sortしてから使う
#define include(y, x, H, W) (0 <= x && x < W && 0 <= y && y < H)
#define square(x) (x) * (x)
#define pb push_back
#define eb emplace_back
#define EPS (1e-10)
#define equals(a,b) (fabs((a) - (b)) < EPS)
#ifndef ONLINE_JUDGE
#define debug1(x) cout << "debug:" << (x) << endl
#define debug2(x, y) cout << "debug:" << (x) << " " << (y) << endl
#define debug3(x, y, z) cout << "debug:" << (x) << " " << (y) << " " << (z) << endl
#define debug4(x, y, z, w) cout << "debug:" << (x) << " " << (y) << " " << (z) << " " << (w) << endl
#define debug5(x, y, z, w, v) cout << "debug:" << (x) << " " << (y) << " " << (z) << " " << (w) << " " << (v) << endl
#define overload5(a, b, c, d, e, f, ...) f
#define debug(...) overload5(__VA_ARGS__, debug5, debug4, debug3, debug2, debug1)(__VA_ARGS__)
#define debug2C(x, y) cout << "debug:" << (x) << " : " << (y) << endl
#define debug3P(x, y, z) cout << "debug:" << (x) << ", " << (y) << " : " << (z) << endl
#define debug3C(x, y, z) cout << "debug:" << (x) << " : " << (y) << ", " << (z) << endl
#define debuga cerr << "a" << endl
#define TIMER_START TIME_START = clock()
#define TIMER_END TIME_END = clock()
#define TIMECHECK cerr << 1000.0 * static_cast<double>(clock() - TIME_START) / CLOCKS_PER_SEC << "ms" << endl
#else
#define debug(x) void(0)
#define debug2(x, y) void(0)
#define debug3(x, y, z) void(0)
#define debug4(x, y, z, w) void(0)
#define debug5(x, y, z, w, v) void(0)
#define debug(...) void(0)
#define debug2C(x, y) void(0)
#define debug3P(x, y, z) void(0)
#define debug3C(x, y, z) void(0)
#define debuga void(0)
#define TIMER_START void(0)
#define TIMER_END void(0)
#define TIMECHECK void(0)
#endif
#define YESNO(bool) if(bool){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
#define yesno(bool) if(bool){cout<<"yes"<<'\n';}else{cout<<"no"<<'\n';}
#define YesNo(bool) if(bool){cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';}
#define POSIMPOS(bool) if(bool){cout<<"POSSIBLE"<<'\n';}else{cout<<"IMPOSSIBLE"<<'\n';}
#define PosImpos(bool) if(bool){cout<<"Possible"<<'\n';}else{cout<<"Impossible"<<'\n';}
#define posimpos(bool) if(bool){cout<<"possible"<<'\n';}else{cout<<"impossible"<<'\n';}
#define popcount __builtin_popcountll // ll は 64bit対応！
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
clock_t TIME_START, TIME_END;
static const double pi = acos(-1.0);
const long long INFL = 1000000000000000000ll;
const long long INFLMAX = numeric_limits< long long >::max(); // 9223372036854775807
const int INF = 1000000000;
const int INFMAX = numeric_limits< int >::max(); // 2147483647
const int mod1 = 1000000007;
const int mod2 = 998244353;
const vi dx1 = {1,0,-1,0};
const vi dy1 = {0,1,0,-1};
const vi dx2 = {0, 1, 1, 1, 0, -1, -1, -1, 0};
const vi dy2 = {1, 1, 0, -1, -1, -1, 0, 1, 1};
const char nl = '\n';
/// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
os << "[";
for (int i = 0; i<vec.size(); i++) {
os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
}
os << "]";
return os;
}
/// pair出力
template<typename T, typename U>
ostream& operator << (ostream& os, pair<T, U>& pair_var) {
os << "(" << pair_var.first << ", " << pair_var.second << ")";
return os;
}
/// map出力
template<typename T, typename U>
ostream& operator << (ostream& os, map<T, U>& map_var) {
os << "{";
for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
os << "(" << itr->first << ", " << itr->second << ")";
itr++;
if(itr != map_var.end()) os << ", ";
itr--;
}
os << "}";
return os;
}
/// set 出力
template<typename T>
ostream& operator << (ostream& os, set<T>& set_var) {
os << "{";
for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
os << *itr;
++itr;
if(itr != set_var.end()) os << ", ";
itr--;
}
os << "}";
return os;
}
int GetTime() {return 1000.0*static_cast<double>(clock() - TIME_START) / CLOCKS_PER_SEC;}
ll myRand(ll B) {return (unsigned long long)rng() % B;}
ll gcd(ll a, ll b) {
if(a < b) swap(a, b);
if(b == 0) return a;
if(a%b == 0) return b;
else return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
assert(gcd(a,b) != 0);
return a / gcd(a, b) * b;
}
/// x % P を非負整数に直す
ll MOD(ll &x, const ll P) {
ll ret = x%P;
if(ret < 0) ret += P;
return x = ret;
}
/// x^n % mod を計算
ll mpow(ll x, ll n, ll mod) {
x %= mod;
ll ret = 1;
while(n > 0) {
if(n & 1) ret = ret * x % mod;
x = x * x % mod;
n >>= 1;
}
return ret;
}
/// x^nを計算
ll lpow(ll x, ll n) {
ll ret = 1;
while(n > 0){
if(n & 1) ret = ret * x;
x = x * x;
n >>= 1;
}
return ret;
}
/// return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
/// 10進数(long long) → 2進数(string)への変換
string toBinary(ll n) {
if(n == 0) return "0";
assert(n > 0);
string ret;
while (n != 0){
ret += ( n & 1 == 1 ? '1' : '0' );
n >>= 1;
}
reverse(ret.begin(), ret.end());
return ret;
}
/// 2進数(string) → 10進数(long long)への変換
ll toDecimal(string S) {
ll ret = 0;
for(int i = 0; i < S.size(); i++){
ret *= 2LL;
if(S[i] == '1') ret += 1;
}
return ret;
}
/// RLE
template <typename C>
vector<pair<typename C::value_type, int> > RunLengthEncoding(C& S) {
using T = typename C::value_type;
if (S.empty()) return {};
vector<pair<T, int> > ret;
T prev = S[0];
int cnt = 1;
for (int i = 1; i < (int)S.size(); i++) {
if (S[i] == prev) cnt++;
else {
ret.emplace_back(prev, cnt);
prev = S[i], cnt = 1;
}
}
ret.emplace_back(prev, cnt);
return ret;
}
/// 二項係数
struct Combination {
int MAX;
int MOD;
vll fac,finv,inv;
Combination(int MAX, int MOD) : MAX(MAX + 1), MOD(MOD) {
fac.resize(MAX + 1);
finv.resize(MAX + 1);
inv.resize(MAX + 1);
COMinit();
}
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
// 二項係数計算
long long COM(int n, int k) {
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
};
/// segment tree (from ACL)
// 型S, 二項演算 S op(S a, S b), 単位元 S e() を定義する必要有、モノイドが対象
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {} // 引数に int n で長さnの数列a(初期値e())を作る
explicit segtree(const std::vector<S>& v) : _n(int(v.size())) { // 引数に vector<S> v で長さn = v.size() の数列a(初期値はvに従う)を作る
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
// a[p]にxを代入（一点更新）
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
// a[p]を返す（一点取得）
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
// op(a[l], ……, a[r-1]) を計算する（区間に対する演算）
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
// op(a[0], ……, a[n-1]) を計算する（全体に対する演算）
S all_prod() const { return d[1]; }
// segment tree 上での二分探索
template <bool (*f)(S)> int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
/// Binary Indexed Tree
template <typename T>
struct BIT {
int n; // 配列の要素数(数列の要素数+1)
vector<T> bit; // データの格納先
BIT(int n_) : n(n_ + 1), bit(n, 0) {} // 1-indexed
// A_i += x
void add(int idx, T x) {
while(idx < n){ // n <- n+1 に予めしてるため等号を含まないことに注意
bit[idx] += x;
idx += (idx & -idx);
}
}
// A_1 ~ A_i の和を計算
T sum(int idx) {
T ret(0);
while(idx > 0){
ret += bit[idx];
idx -= (idx & -idx);
}
return ret;
}
// A_1 + A_2 + ... + A_x >= w となるような最小の x を求める (A_i >= 0)
int lower_bound(T w) {
if (w <= 0) return 0;
else {
int x = 0, r = 1;
while (r < n) r = r << 1;
for (int len = r; len > 0; len = len >> 1) {
if (x + len < n && bit[x + len] < w) {
w -= bit[x + len];
x += len;
}
}
return x + 1;
}
}
};
/// Union-Find
struct unionfind{
vector<int> par, siz;
unionfind(int n) : par(n, -1), siz(n, 1) {}
// 根を求める
int root(int x) {
if (par[x] == -1) return x;
else return par[x] = root(par[x]);
}
// xとyの根（グループ）が一致するかどうか
bool issame(int x, int y){
return root(x) == root(y);
}
// xとyのグループの併合
bool unite(int x, int y){
x = root(x); y = root(y);
if (x == y) return false;
if (siz[x] < siz[y]) swap(x,y);
par[y] = x;
siz[x] += siz[y];
return true;
}
// xを含むグループのサイズ
int size(int x){
return siz[root(x)];
}
};
// ############################
// # #
// # C O D E S T A R T #
// # #
// ############################
/// 行列同士の積
template<typename T>
vector<vector<T> > matrix_prod(vector<vector<T> > &A, vector<vector<T> > &B){
// Aは i * k , Bは k * j の行列 -> 積で i * j の行列を返す
assert(A[0].size() == B.size());
int r = A.size();
int c = B[0].size();
vector<vector<T> > ret(r, vector<T>(c,0));
rep(i,r){
rep(j,c){
rep(k,B.size()){
ret[i][j] += A[i][k] * B[k][j];
}
}
}
return ret;
}
void solve() {
vvi A(2, vi(2));
rep(i,2) rep(j,2) cin >> A[i][j];
vvi AA = matrix_prod(A, A);
vvi ans = matrix_prod(A, AA);
rep(i,2) {
rep(j,2) cout << ans[i][j] << " ";
cout << nl;
}
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
TIMER_START;
//cout << fixed << setprecision(15);
int tt;
tt = 1;
//cin >> tt;
while(tt--){
solve();
}
TIMER_END;
TIMECHECK;
return 0;
}